排序算法之堆排序（Heapsort）解析

no_mkd

一.堆排序的优缺点（pros and cons）

（还是简单的说说这个，毕竟没有必要浪费时间去理解一个糟糕的的算法）

优点：

1. 堆排序的效率与快排、归并相同，都达到了基于比较的排序算法效率的峰值（时间复杂度为O(nlogn)）
2. 除了高效之外，最大的亮点就是只需要O(1)的辅助空间了，既最高效率又最节省空间，只此一家了
3. 堆排序效率相对稳定，不像快排在最坏情况下时间复杂度会变成O(n^2)），所以无论待排序序列是否有序，堆排序的效率都是O(nlogn)不变（注意这里的稳定特指平均时间复杂度=最坏时间复杂度，不是那个“稳定”，因为堆排序本身是不稳定的）

缺点：（从上面看，堆排序几乎是完美的，那么为什么最常用的内部排序算法是快排而不是堆排序呢？）

1. 最大的也是唯一的缺点就是——堆的维护问题，实际场景中的数据是频繁发生变动的，而对于待排序序列的每次更新（增，删，改），我们都要重新做一遍堆的维护，以保证其特性，这在大多数情况下都是没有必要的。（所以快排成为了实际应用中的老大，而堆排序只能在算法书里面顶着光环，当然这么说有些过分了，当数据更新不很频繁的时候，当然堆排序更好些...）

二.内部原理

首先要知道堆排序的步骤：

1. 构造初始堆，即根据待排序序列构造第一个大根堆或者小根堆（大根堆小根堆是什么？这个不解释了，稻草垛知道吧..）
2. 首尾交换，断尾重构，即对断尾后剩余部分重新构造大（小）根堆
3. 重复第二步，直到首尾重叠，排序完成

按小根堆排序结果是降序（或者说是非升序，不要在意这种细节..），按大根堆排序的结果是升序

上面这句话乍看好像不对（小根堆中最小元素在堆顶，数组组堆顶元素就是a[0]，怎么会是降序？），不过不用质疑这句话的正确性，看了下面这几幅图就明白了：

假设待排序序列是a[] = {7, 1, 6, 5, 3, 2, 4}，并且按大根堆方式完成排序

第一步（构造初始堆）：

{7, 5, 6, 1, 3, 2, 4}已经满足了大根堆，第一步完成

第二步（首尾交换，断尾重构）：

第三步（重复第二步，直至所有尾巴都断下来）：

无图，眼睛画瞎了，mspaint实在不好用。。到第二步应该差不多了吧，剩下的用笔也就画出来了。。

其实核心就是“断尾”，但可悲的是所有的资料上都没有明确说出来，可是，还有比“断尾”更贴切的描述吗？

三.实现细节

原理介绍中给出的图基本上也说清楚了实现细节，所以这里只关注代码实现

首先是自己写出来的大根堆方式实现：

#include<stdio.h>
//构造大根堆（让a[m]到a[n]满足大根堆）
void HeapAdjust(int a[], int m, int n){
int temp;
int max;
int lc;//左孩子
int rc;//右孩子
while(1){
	//获取a[m]的左右孩子
	lc = 2 * m + 1;
	rc = 2 * m + 2;
	//比较a[m]的左右孩子，max记录较大者的下标
	if(lc &gt;= n){
		break;//不存在左孩子则跳出
	}
	if(rc &gt;= n){
		max = lc;//不存在右孩子则最大孩子为左孩子
	}
	else{
		max = a[lc] &gt; a[rc] ? lc : rc;//左右孩子都存在则找出最大孩子的下标
	}
	//判断并调整（交换）
	if(a[m] &gt;= a[max]){//父亲比左右孩子都大，不需要调整，直接跳出
		break;
	}
	else{//否则把小父亲往下换
		temp = a[m];
		a[m] = a[max];
		a[max] = temp;
		//准备下一次循环，注意力移动到孩子身上，因为交换之后以孩子为根的子树可能不满足大根堆
		m = max;
	}
}

}
void HeapSort(int a[], int n){
int i,j;
int temp;
//自下而上构造小根堆（初始堆）
for(i = n / 2 - 1;i &gt;= 0;i--){//a[n/2 - 1]恰好是最后一个非叶子节点（叶子节点已经满足小根堆，只需要调整所有的非叶子节点），一点小小的优化
	HeapAdjust(a, i, n);
}

printf("初始堆: ");
for(i = 0;i &lt; n;i++){
	printf("%d ", a[i]);
}
printf("\n");

for(i = n - 1;i &gt; 0;i--){
	//首尾交换，断掉尾巴
	temp = a[i];
	a[i] = a[0];
	a[0] = temp;
	//断尾后的部分重新调整
	HeapAdjust(a, 0, i);

	/*
	printf("第%d次（i - 1 = %d）: ", n - i, i - 1);
	for(j = 0;j &lt; n;j++){
		printf("%d ", a[j]);
	}
	printf("\n");
	*/
}

}
main(){
//int a[] = {5, 6, 3, 4, 1, 2, 7};
//int a[] = {1, 2, 3, 4, 5, 6, 7};
//int a[] = {7, 6, 5, 4, 3, 2, 1};
int a[] = {7, 1, 6, 5, 3, 2, 4};
int m, n;
int i;
m = 0;
n = sizeof(a) / sizeof(int);
//HeapAdjust(a, m, n);
HeapSort(a, n);
printf("结果: ");
for(i = 0;i &lt; n;i++){
	printf("%d ", a[i]);
}
printf("\n");

}

P.S.代码中注释极其详尽，因为是完全一步一步自己想着写出来的，应该不难理解。看代码说话，在此多说无益。

接下来给出书本上的大根堆方式实现：

#include<stdio.h>
void HeapAdjust(int a[], int m, int n){
int i;
int t = a[m];
for(i = 2 * m + 1;i &lt;= n;i = 2 * i + 1){
	if(i &lt; n &amp;&amp; a[i + 1] &gt; a[i])++i;
	if(t &gt;= a[i])break;
	//把空缺位置往下放
	a[m] = a[i];
	m = i;
}
a[m] = t;//只做一次交换，步骤上的优化

}
void HeapSort(int a[], int n){
int i;
int t;
//自下而上构造大根堆
for(i = n / 2 - 1;i &gt;= 0;--i){
	HeapAdjust(a, i, n - 1);
}

printf("初始堆: ");
for(i = 0;i &lt; n;i++){
	printf("%d ", a[i]);
}
printf("\n");

for(i = n - 1;i &gt; 0;i--){
	//首尾交换，断掉尾巴
	t = a[i];
	a[i] = a[0];
	a[0] = t;
	//对断尾后的部分重新建堆
	HeapAdjust(a, 0, i - 1);
}

}
main(){
//int a[] = {5, 6, 3, 4, 1, 2, 7};
//int a[] = {1, 2, 3, 4, 5, 6, 7};
//int a[] = {7, 6, 5, 4, 3, 2, 1};
int a[] = {7, 1, 6, 5, 3, 2, 4};
int m, n;
int i;
m = 0;
n = sizeof(a) / sizeof(int);
//HeapAdjust(a, m, n);
HeapSort(a, n);
printf("结果: ");
for(i = 0;i &lt; n;i++){
	printf("%d ", a[i]);
}
printf("\n");

}

P.S.书本上的代码短了不少，不仅仅是篇幅上的优化，也有实实在在的步骤上的优化，细微差别也在注释中说明了。但这种程度的优化却使得代码的可读性大大降低，所以一次次拿起算法书，又一次次放下。。（实际应用中我们可以对书本上的代码做形式上的优化，在保持其高效性的同时尽可能的提升其可读性。。）

最后是在研究过书本上的算法之后，结合其优化措施，写出的小根堆方式实现（网上的资料多是大根堆方式的，其实原理都一样，这里只是为了避免枯燥无趣。。）：

#include<stdio.h>
//构造小根堆（让a[m]到a[n]满足小根堆）
void HeapAdjust(int a[], int m, int n){
int i;
int t = a[m];
int temp;
for(i = 2 * m + 1;i &lt;= n;i = 2 * i + 1){
	//a[m]的左右孩子比较，i记录较小者的下标
	if(i &lt; n &amp;&amp; a[i + 1] &lt; a[i]){
		i = i + 1;
	}
	if(t &lt;= a[i]){
		break;
	}
	else{//把空缺位置往下换
		//把较小者换上去
		temp = a[m];
		a[m] = a[i];
		a[i] = temp;
		//准备下一次循环
		m = i;
	}
}

}
void HeapSort(int a[], int n){
int i, j;
int temp;
//自下而上构造小根堆（初始堆）
for(i = n / 2 - 1;i &gt;= 0;i--){//a[n/2 - 1]恰好是最后一个非叶子节点（叶子节点已经满足小根堆，只需要调整所有的非叶子节点），一点小小的优化
	HeapAdjust(a, i, n);
}

printf("初始堆: ");
for(i = 0;i &lt; n;i++){
	printf("%d ", a[i]);
}
printf("\n");

//把每个元素都调整到应该去的位置
for(i = n - 1; i &gt; 0;i--){
	//首尾交换
	temp = a[i];
	a[i] = a[0];
	a[0] = temp;
	//断尾后剩余部分重新调整
	HeapAdjust(a, 0, i - 1);
}

}
main(){
//int a[] = {7, 6, 5, 4, 3, 2, 1};
//int a[] = {1, 5, 6, 4, 3, 2, 7};
int a[] = {1, 2, 3, 4, 5, 6, 7};
int m, n;
int i;
m = 0;
n = sizeof(a) / sizeof(int);
//HeapAdjust(a, m, n);
HeapSort(a, n);
printf("结果: ");
for(i = 0;i &lt; n;i++){
	printf("%d ", a[i]);
}
printf("\n");

}

P.S.注释依然详尽，看代码，不废话

四.总结

堆排序的步骤就几个字而已：建堆 -> 首尾交换，断尾重构 -> 重复第二步，直到断掉所有尾巴

还有比这更清晰更明了的描述吗？

到现在我们已经掌握了几个有用的排序算法了：

快速排序、归并排序、堆排序

那么实际应用中要如何选择呢？有这些选择标准：

1. 若n较小，采用插入排序和简单选择排序。由于直接插入排序所需的记录移动操作比简单选择排序多，所以当记录本身信息量比较大时，用简单选择排序更好。
2. 若待排序序列基本有序，可以采用直接插入排序或者冒泡排序
3. 若n较大，应该采用时间复杂度最低的算法，比如快排，堆排或者归并
4. • 细分的话，当数据随机分布时，快排最佳（这与快排的硬件优化有关，在之前的博文中有提到过）
   • 堆排只需要一个辅助空间，而且不会出现快排的最坏情况
   • 快排和堆排都是不稳定的，如果要求稳定的话可以采用归并，还可以把直接插入排序和归并结合起来，先用直接插入获得有序碎片，再归并，这样得到的结果也是稳定的，因为直接插入是稳定的

说明：在理解“断尾”的过程中参考了前辈的博文，特此感谢