排序算法之堆排序(Heapsort)解析

一.堆排序的优缺点(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 >= n){
			break;//不存在左孩子则跳出
		}
		if(rc >= n){
			max = lc;//不存在右孩子则最大孩子为左孩子
		}
		else{
			max = a[lc] > a[rc] ? lc : rc;//左右孩子都存在则找出最大孩子的下标
		}
		//判断并调整(交换)
		if(a[m] >= 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 >= 0;i--){//a[n/2 - 1]恰好是最后一个非叶子节点(叶子节点已经满足小根堆,只需要调整所有的非叶子节点),一点小小的优化
		HeapAdjust(a, i, n);
	}

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

	for(i = n - 1;i > 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 < 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 < 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 <= n;i = 2 * i + 1){
		if(i < n && a[i + 1] > a[i])++i;
		if(t >= 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 >= 0;--i){
		HeapAdjust(a, i, n - 1);
	}

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

	for(i = n - 1;i > 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 < 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 <= n;i = 2 * i + 1){
		//a[m]的左右孩子比较,i记录较小者的下标
		if(i < n && a[i + 1] < a[i]){
			i = i + 1;
		}
		if(t <= 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 >= 0;i--){//a[n/2 - 1]恰好是最后一个非叶子节点(叶子节点已经满足小根堆,只需要调整所有的非叶子节点),一点小小的优化
		HeapAdjust(a, i, n);
	}

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

	//把每个元素都调整到应该去的位置
	for(i = n - 1; i > 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 < n;i++){
		printf("%d ", a[i]);
	}
	printf("\n");
}

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

四.总结

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

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

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

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

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

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

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

排序算法之堆排序(Heapsort)解析》上有1条评论

发表评论

电子邮件地址不会被公开。 必填项已用*标注

*

code