数据结构与算法|数据结构与算法之堆排序算法|数据结构

数据结构与算法之堆排序

- 前提条件
- 基本概念
- 算法步骤
- - 建立大根堆
  - 堆排序
- 算法分析
- - 时间复杂度
  - 空间复杂度
- 算法特点
- 完整代码
- - 输出结果
- 参考文献

前提条件

熟悉C语言与指针

熟悉数据结构与算法

基本概念

堆排序 (Heap Sort) 是一种树形选择排序，在排序过程中，将待排序的记录 r [ l . . n ] r[l..n] r[l..n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲结点和孩子结点之间的内在关系，在当前无序的序列中选择关键字最大（或最小）的记录。

算法步骤建立大根堆

【数据结构与算法|数据结构与算法之堆排序】建立大根堆

//筛选法调整堆 void HeapAdjust(SqList &L,int s,int m) {//假设r[s+1..m]已经是堆，将r[s..m]调整为以r[s]为根的大根堆 ElemType rc; int j; rc=L.r[s]; for(j=2*s; j<=m; j*=2) { //沿key较大的孩子结点向下筛选 if(j=L.r[j].key) break; //rc应插入在位置s上 L.r[s]=L.r[j]; s=j; } L.r[s]=rc; //插入 } //建初堆 void CreatHeap(SqList &L) { //把无序序列L.r[1..n]建成大根堆 int i,n; n=L.length; //printf("%d",n); for(i=n/2; i>0; --i)//反复调用HeapAdjust HeapAdjust(L,i,n); }//CreatHeap

堆排序
堆排序利用了大根堆（或小根堆）堆顶记录的关键字最大（或最小）这一特征，使得当前无序的序列中选择关键字最大（或最小）的记录变得简单。下面讨论用大根堆进行排序，堆排序的步骤如下。

①按堆的定义将待排序序列r[1…n]调整为大根堆（这个过程称为建初堆)，交换r[1]和r[n],则r[n]为关键字最大的记录。
②将r[1…n-1]重新调整为堆,交换r[1]和r[n-1]，则r[n-1]为关键字次大的记录。
③循环n-1次，直到交换了r[1]和r[2]为止，得到了一个非递减的有序序列r[1 …n]。

堆排序

void HeapSort(SqList &L) { //对顺序表L进行堆排序 int i; ElemType x; CreatHeap(L); //把无序序列L.r[1..L.length]建成大根堆 for(i=L.length; i>1; --i) {x=L.r[1]; //将堆顶记录和当前未经排序子序列L.r[1..i]中最后一个记录互换 L.r[1]=L.r[i]; L.r[i]=x; HeapAdjust(L,1,i-1); //将L.r[1..i-1]重新调整为大根堆 }//for }//HeapSort

算法分析时间复杂度

堆排序的运行时间主要耗费在建初堆和调整堆时进行的反复“筛选”上。

设有n个记录的初始序列所对应的完全二叉树的深度为h，建初堆时，每个非终端结点都要自上而下进行“筛选"。由于第i层上的结点数小于等于 2 i ? 1 2^{i-1} 2i?1,且第i层结点最大下移的深度为h-i,每下移一层要做两次比较，所以建初堆时关键字总的比较次数为 ∑ i = h ? 1 i 2 i ? 1 ? 2 ( h ? i ) = ∑ i = h ? 1 i 2 i ? 2 ( h ? i ) = ∑ j = 1 h ? 1 2 h ? j ? j < = 2 n ∑ j = 1 h ? 1 j / 2 j < = 4 n \sum\limits_{i=h-1}^i 2^{i-1}\cdot2(h-i)=\sum\limits_{i=h-1}^i 2^{i}\cdot2(h-i)=\sum\limits_{j=1}^{h-1} 2^{h-j}\cdot j<=2n\sum\limits_{j=1}^{h-1}j/2^j<=4n\quad i=h?1∑i?2i?1?2(h?i)=i=h?1∑i?2i?2(h?i)=j=1∑h?1?2h?j?j<=2nj=1∑h?1?j/2j<=4n
调整建新堆时要做 n-1次“筛选” ，每次“筛选”都要将根结点下移到合适的位置。 n个结点的完全二叉树的深度为 └ l o g 2 n ┘ + 1 \llcorner log_2n\lrcorner+1 └log2?n┘+1，则重建堆时关键字总的比较次数不超过
2 ( └ l o g 2 ( n ? 1 ) ┘ + └ l o g 2 ( n ? 2 ) ┘ + . . . + └ l o g 2 2 ┘ ) < 2 n ( └ l o g 2 n ┘ ) 2(\llcorner log_2(n-1)\lrcorner+\llcorner log_2(n-2)\lrcorner+...+\llcorner log_22\lrcorner)<2n(\llcorner log_2n\lrcorner) 2(└log2?(n?1)┘+└log2?(n?2)┘+...+└log2?2┘)<2n(└log2?n┘)

由此，堆排序在最坏的情况下，其时间复杂度也为 O ( n l o g 2 n ) O(nlog_{2}n) O(nlog2?n)。

实验研究表明，平均性能接近于最坏性能。

空间复杂度

仅需一个记录大小供交换用的辅助存储空间，所以空间复杂度为O(1)。

算法特点

(1)是不稳定排序。

(2)只能用于顺序结构,不能用于链式结构。

(3)初始建堆所需的比较次数较多，因此记录数较少时不宜采用。堆排序在最坏情况下时间复杂度为 O ( n l o g 2 n ) O(nlog_{2}n) O(nlog2?n)，相对于快速排序最坏情况下的 O ( n 2 ) O(n^2) O(n2)而言是一个优点，当记录较多时较为高效。

完整代码

//堆排序 #include #include #defineMAXSIZE20//顺序表的最大长度 typedef struct { int key; char *otherinfo; }ElemType; //顺序表的存储结构 typedef struct {ElemType *r; //存储空间的基地址 intlength; //顺序表长度 }SqList; //顺序表类型//筛选法调整堆 void HeapAdjust(SqList &L,int s,int m) {//假设r[s+1..m]已经是堆，将r[s..m]调整为以r[s]为根的大根堆 ElemType rc; int j; rc=L.r[s]; for(j=2*s; j<=m; j*=2) { //沿key较大的孩子结点向下筛选 if(j=L.r[j].key) break; //rc应插入在位置s上 L.r[s]=L.r[j]; s=j; } L.r[s]=rc; //插入 } //HeapAdjust void Create_Sq(SqList &L) { int i,n; printf("请输入数据个数，不超过%d个\n",MAXSIZE); scanf("%d",&n); //输入个数 while(n>MAXSIZE) {printf("个数超过上限，不能超过%d，请重新输入",MAXSIZE); scanf("%d",&n); } printf("请输入待排序的数据:\n"); for(i=1; i<=n; i++) {scanf("%d",&L.r[i].key); L.length++; } }//建初堆 void CreatHeap(SqList &L) { //把无序序列L.r[1..n]建成大根堆 int i,n; n=L.length; //printf("%d",n); for(i=n/2; i>0; --i)//反复调用HeapAdjust HeapAdjust(L,i,n); }//CreatHeapvoid HeapSort(SqList &L) { //对顺序表L进行堆排序 int i; ElemType x; CreatHeap(L); //把无序序列L.r[1..L.length]建成大根堆 for(i=L.length; i>1; --i) {x=L.r[1]; //将堆顶记录和当前未经排序子序列L.r[1..i]中最后一个记录互换 L.r[1]=L.r[i]; L.r[i]=x; HeapAdjust(L,1,i-1); //将L.r[1..i-1]重新调整为大根堆 }//for }//HeapSort void show(SqList L) { int i; for(i=1; i<=L.length; i++) printf("%d ",L.r[i].key); } int main() { SqList L; L.r=(ElemType*)malloc((MAXSIZE+1)*sizeof(ElemType)); L.length=0; Create_Sq(L); //创建一个顺序表，里面存储着要排序的初始序列 HeapSort(L); //对初始序列进行堆排序 printf("排序后的结果为:\n"); show(L); //输出排序后的结果为 return 0; }

输出结果

文章图片

参考文献 [1] 严蔚敏，吴伟民. 数据结构（C语言版）. 北京：清华大学出版社，2020
[2] 严蔚敏，李冬梅，吴伟民. 数据结构（C语言版）（第二版）. 北京：人民邮电出版社，2021
[3] 吴伟民，李小妹，刘添添，黄剑锋，苏庆，林志毅，李杨.数据结构. 北京：高等教育出版社，2017
[4] 王道论坛. 2022数据结构考研复习指导. 北京：电子工业出版社，2021