linux实验报告1
需积分: 0 162 浏览量
2022-08-08
18:18:39
上传
评论
收藏 21KB DOCX 举报
Linux 实验
班级
姓名
学号
硬件二班
张东琪
161403204
堆排序
堆排序是利用堆的性质进行的一种选择排序。下面先讨论一下堆。
1.堆
堆实际上是一棵完全二叉树，其任何一非叶节点满足性质：
Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者
Key[i]>=Key[2i+1]&&key>=key[2i+2]
即任何一非叶节点的关键字不大于或者不小于其左右孩子节点的关键字。
堆分为大顶堆和小顶堆，满足 Key[i]>=Key[2i+1]&&key>=key[2i+2]称为大顶堆，
满足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]称为小顶堆。由上述性质可知大顶堆
的堆顶的关键字肯定是所有关键字中最大的，小顶堆的堆顶的关键字是所有关键字中最小的。
2.堆排序的思想
利用大顶堆(小顶堆)堆顶记录的是最大关键字(最小关键字)这一特性，使得每次从无序中
选择最大记录(最小记录)变得简单。
其基本思想为(大顶堆)：
1)将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无须区；
2)将堆顶元素 R[1]与最后一个元素 R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)
和新的有序区(Rn),且满足 R[1,2...n-1]<=R[n];
3)由于交换后新的堆顶 R[1]可能违反堆的性质，因此需要对当前无序区
(R1,R2,......Rn-1)调整为新堆，然后再次将 R[1]与无序区最后一个元素交换，得到新的
无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。不断重复此过程直到有序区的元素个数
为 n-1，则整个排序过程完成。
操作过程如下：
1)初始化堆：将 R[1..n]构造为堆；
2)将当前无序区的堆顶元素 R[1]同该区间的最后一个记录交换，然后将新的无序区调
整为新的堆。
因此对于堆排序，最重要的两个操作就是构造初始堆和调整堆，其实构造初始堆事实上
也是调整堆的过程，只不过构造初始堆是对所有的非叶节点都进行调整。
#include<stdio.h>
葡萄的眼泪
- 粉丝: 16
- 资源: 303
最新资源
- 华为HCIA-WLAN 3.0 课程视频（45 STA无法上线故障排查.mp4）
- 华为HCIA-WLAN 3.0 课程视频（44 AP无法上线故障排查（下）.mp4）
- 华为HCIA-WLAN 3.0 课程视频（43 AP无法上线故障排查（上）.mp4）
- python实现基于U-net和MRI图像的膀胱壁边缘以及膀胱肿瘤检测（高准确率）+源码+开发文档+模型训练（毕业设计&课程设计
- 华为HCIA-WLAN 3.0 课程视频（42 WLAN系统维护的方法及故障处理命令.mp4）
- 华为HCIA-WLAN 3.0 课程视频（41 WLAN故障处理一般流程（下）.mp4）
- C++基于OpenCV+Qt的人脸识别考勤系统-毕业设计+源代码+文档说明.zip
- python爬虫资源下载
- 华为HCIA-WLAN 3.0 课程视频（40 WLAN故障处理一般流程（上）.mp4）
- PHP教材管理系统设计（源码+数据库）
资源上传下载、课程学习等过程中有任何疑问或建议，欢迎提出宝贵意见哦~我们会及时处理！
点击此处反馈
评论0