()
00-1010在前一章中,我们已经详细介绍了排序的相关概念(学习笔记-排序简介),本文旨在详细介绍堆排序。
本文目的
Heapsort(英文:heap)是指利用堆的数据结构设计的一种排序算法。堆是一种近乎完整的二叉树结构,同时满足堆的性质:即子节点的键值或索引总是小于(或大于)其父节点。00-1010 Heap是计算机科学中一种特殊数据结构的总称。堆是一种非线性结构。堆可以被视为一个数组或一个完整的二叉树。一般来说,堆实际上是一个由完整二叉树结构维护的一维数组。这里所用的堆一般指大顶堆或小顶堆。
大堆
每个节点的值大于或等于其左右子节点的值,称为大顶堆。如下图所示。
定堆
每个节点的值小于或等于其左右子节点的值,这称为小顶堆。如下图所示。
堆排序
构造要排序的序列成为一个大的顶堆,此时,整个序列的最大值就是堆顶的根节点。与最后一个元素交换,此时结束为最大值。然后,剩余的n-1个元素被重建成一个堆,从而可以获得n个元素的下一个最小值。在重复执行之后,可以获得有序序列。需要注意的是,大顶堆是从最后一个非叶节点开始自下而上调整的。
堆是什么
1.创建堆R [0.n-1];2.交换头部(最大值)和尾部;
3.将堆的大小减少1(已经订购的部分不会进入下一轮);
4.重复步骤2,直到堆的大小为1。
算法原理
操作流程如下:1.初始化堆:构造R[1.n]作为一堆;
2.将当前无序区堆的顶部元素R[1]与区间的最后一条记录进行交换,然后将新的无序区调整为新的堆。
#包含stdio.h
#定义元素类型int /*元素类型*/
int k=1;//回合记录
//打印功能
无效打印(elemType arr[],int len){ 0
int I;
for(I=0;伊琳;I){ 0
printf ('%d\t ',arr[I]);
}
printf(' \ n ');
}
//记录交换
无效交换(int* a,int* b)
{
int temp=* b;
* b=* a;
*a=温度;
}
//建一个大的顶桩
void max_heapify(int a[],int start,int end)
{
//创建父节点指示器和子节点指示器
int dad=start
int son=dad * 2 1;
//仅当子节点指标在范围内时比较。
while (son=end)
if (son 1=end a[son] a[son 1]) {
//首先比较两个子节点的大小,选择最大的一个。
儿子;
}
//如果父节点大于子节点,说明调整完成,直接跳出功能。
如果(父亲[儿子])
返回;
}else{
//否则,交换父子内容,继续子节点和孙子节点的比较。
互换(一个[爸爸],一个[儿子]);
爸爸=儿子;
儿子=爸爸* 2 1;
}
}
}
//排序
void Sort(elemType a[],int len)
{
int I;
//初始化,我从最后一个父节点开始调整
for(I=len/2-1;I=0;I-){ 0
max_heapify(a,I,len-1);
}
for(I=len-1;I 0;i -)
{
//首先将第一个元素与前一个排列好的元素交换,然后重新调整,直到排序完成。
swap(a[0],a[I]);
max_heapify(a,0,I-1);
Printf('第一个==% d===轮次排序后的结果如下:\n ',k);
打印(a,9);
k=k1;
}
}
int main(){ 0
int I;
elemType arr[9]={94,19,29,9,11,1,14,13,29 };
Printf('要排序的序列是:\ n ');
印刷(arr,9);
printf(' \ n \ n ');
排序(arr,9);
printf(' \ n \ n ');
Printf('排序结果如下:\ n ');
印刷(arr,9);
}
00-1010时间复杂度
堆排序的运行时间主要消耗在堆构建和堆重构时的重复筛选上。在堆构建的过程中,由于我们从完全二叉树的最低非叶节点开始,所以我们将其与其子节点进行比较,并根据需要进行交换。对于每个非叶节点,实际上最多有两次比较和交换,因此初始化堆的时间复杂度是O(n)。在形式排序中,第I次取堆顶记录并重建堆需要O(logi)时间(完整二叉树的一个节点到根节点的距离为log2i 1),取堆顶记录需要n-1次,因此重建堆的时间复杂度为O(nlogn)。一般来说,堆排序的时间复杂度为O(nlogn)。因为堆排序对元素记录的排序状态不敏感,所以它的最佳、最差和平均时间复杂度都是O(nlogn)。
空间复杂性
在堆中交换元素时只有一个辅助空间,与问题规模无关,空间复杂度为O(1)。
分选稳定性
在堆构建过程中,无法保证构建前后相同值的相对位置,因此堆排序不稳定。
本文初衷是分享学习笔记,部分图文来源于网络,如侵删。