一、前言
堆排序是一种选择排序。
选择排序：每趟从待排序的记录中选出关键字最小的记录，顺序放在已排序的记录序列末尾，直到全部排序结束为止。
二、算法思想
堆排序是利用堆的性质进行的一种选择排序。
动态效果示意图：
堆是一棵顺序存储的完全二叉树。
- 其中每个结点的关键字都不大于其孩子结点的关键字，这样的堆称为小根堆。
- 其中每个结点的关键字都不小于其孩子结点的关键字，这样的堆称为大根堆。
举例来说，对于n个元素的序列{R0, R1, ... , Rn}当且仅当满足下列关系之一时，称之为堆：
- Ri <= R2i+1 且 Ri <= R2i+2 (小根堆)
- Ri >= R2i+1 且 Ri >= R2i+2 (大根堆)
其中i=1,2,…,n/2向下取整；
如上图所示，序列R{3, 8, 15, 31, 25}是一个典型的小根堆。
堆中有两个结点，元素3和元素8。
元素3在数组中以R[0]表示，它的左孩子结点是R[1]，右孩子结点是R[2]。
元素8在数组中以R[1]表示，它的左孩子结点是R[3]，右孩子结点是R[4]，它的父结点是R[0]。可以看出，它们满足以下规律：
设当前元素在数组中以R[i]表示，那么，
(1) 它的左孩子结点是：R[2*i+1];
(2) 它的右孩子结点是：R[2*i+2];
(3) 它的父结点是：R[(i-1)/2];
(4) R[i] <= R[2*i+1] 且 R[i] <= R[2i+2]。
首先，按堆的定义将数组R[0..n]调整为堆（这个过程称为创建初始堆），交换R[0]和R[n]；
然后，将R[0..n-1]调整为堆，交换R[0]和R[n-1]；
如此反复，直到交换了R[0]和R[1]为止。
以上思想可归纳为两个操作：
（1）根据初始数组去构造初始堆（构建一个完全二叉树，保证所有的父结点都比它的孩子结点数值大）。
（2）每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。
当输出完最后一个元素后，这个数组已经是按照从小到大的顺序排列了。
先通过详细的实例图来看一下，如何构建初始堆。
设有一个无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 }。
构造了初始堆后，我们来看一下完整的堆排序处理：
还是针对前面提到的无序序列 { 1, 3, 4, 5, 2, 6, 9, 7, 8, 0 } 来加以说明。
相信，通过以上两幅图，应该能很直观的演示堆排序的操作处理。
看完上面所述的流程你至少有一个疑问：
- 如何确定最后一个非叶子结点？
其实这是有一个公式的，设二叉树结点总数为 n，则最后一个非叶子结点是第 ⌊n/2⌋ 个。
1、代码
C++：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 | #include <iostream> #include <vector> using namespace std; void HeapAdjust(vector<int> &list, int parent, int length){ int temp = list[parent]; // temp保存当前父节点 int child = 2 * parent + 1; // 先获得左孩子 while (child < length){ // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点 if (child + 1 < length && list[child] < list[child + 1]){ child++; } // 如果有右孩子结点，并且右孩子结点的值大于左孩子结点，则选取右孩子结点 if (temp >= list[child]){ break; } // 把孩子结点的值赋给父结点 list[parent] = list[child]; // 选取孩子结点的左孩子结点,继续向下筛选 parent = child; child = 2 * parent + 1; } list[parent] = temp; } vector<int> HeadSort(vector<int> list){ int length = list.size(); // 循环建立初始堆 for (int i = length / 2 - 1; i >= 0; i--){ HeapAdjust(list, i, length); } // 进行n-1次循环，完成排序 for (int i = length - 1; i > 0; i--){ // 最后一个元素和第一元素进行交换 int temp = list[i]; list[i] = list[0]; list[0] = temp; // 筛选 R[0] 结点，得到i-1个结点的堆 HeapAdjust(list, 0, i); cout << "第" << length - i << "趟排序:"; for (int i = 0; i < list.size(); i++){ cout << list[i] << " "; } cout << endl; } return list; } void main(){ int arr[] = { 6, 4, 8, 9, 2, 3, 1 }; vector<int> test(arr, arr + sizeof(arr) / sizeof(arr[0])); cout << "排序前:"; for (int i = 0; i < test.size(); i++){ cout << test[i] << " "; } cout << endl; vector<int> result; result = HeadSort(test); cout << "排序后:"; for (int i = 0; i < result.size(); i++){ cout << result[i] << " "; } cout << endl; system("pause"); } |
运行结果如下：
Python：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 | # -*- coding:utf-8 -*- def HeadSort(input_list): ''' 函数说明:堆排序（升序） Author: www.cuijiahua.com Parameters: input_list - 待排序列表 Returns: sorted_list - 升序排序好的列表 ''' def HeadAdjust(input_list, parent, length): ''' 函数说明:堆调整，调整为最大堆 Author: www.cuijiahua.com Parameters: input_list - 待排序列表 parent - 堆的父结点 length - 数组长度 Returns: 无 ''' temp = input_list[parent] child = 2 * parent + 1 while child < length: if child + 1 < length and input_list[child] < input_list[child+1]: child += 1 if temp >= input_list[child]: break input_list[parent] = input_list[child] parent = child child = 2 * parent + 1 input_list[parent] = temp if len(input_list) == 0: return [] sorted_list = input_list length = len(sorted_list) for i in range(0, length // 2)[::-1]: HeadAdjust(sorted_list, i, length) for j in range(1, length)[::-1]: temp = sorted_list[j] sorted_list[j] = sorted_list[0] sorted_list[0] = temp HeadAdjust(sorted_list, 0, j) print('第%d趟排序:' % (length - j), end = '') print(sorted_list) return sorted_list if __name__ == '__main__': input_list = [6, 4, 8, 9, 2, 3, 1] print('排序前:', input_list) sorted_list = HeadSort(input_list) print('排序后:', sorted_list) |
运行结果同上。
三、算法分析
1、堆排序算法的总体情况
2、时间复杂度
首先计算建堆的时间，也就是下面的代码，
1 2 3 4 | // 循环建立初始堆 for (int i = length / 2; i >= 0; i--){ HeapAdjust(list, i, length); } |
n 个结点，从第 0 层至第 logn 层。对于第 i 层的 2i 个点如果需要往下走 logn−i 步，那么把走的所有步相加得：
接下来就是排序的时间，即下面的代码：
1 2 3 4 5 6 7 8 9 10 | // 进行n-1次循环，完成排序 for (int i = length - 1; i > 0; i--){ // 最后一个元素和第一元素进行交换 int temp = list[i]; list[i] = list[0]; list[0] = temp; // 筛选 R[0] 结点，得到i-1个结点的堆 HeapAdjust(list, 0, i); } |
HeapAdjust() 耗时 logn，共 n 次，故排序时间为 O(nlogn)。
堆的存储表示是顺序的。因为堆所对应的二叉树为完全二叉树，而完全二叉树通常采用顺序存储方式。
当想得到一个序列中第k个最小的元素之前的部分排序序列，最好采用堆排序。
3、算法稳定性
堆排序是一种不稳定的排序方法。
因为在堆的调整过程中，关键字进行比较和交换所走的是该结点到叶子结点的一条路径，因此对于相同的关键字就可能出现排在后面的关键字被交换到前面来的情况。
本站整理自：
2018年7月31日 下午10:53 沙发
18行的break是跳出while循环吗？为啥呢？此时仅仅是当前父节点大于左右子节点啊，为啥不继续向下调整而直接跳出？
2018年8月1日 上午10:56 1层
@到底对不对 直接退出while循环啊 ，因为已经找到不满足要求的两个节点了，对它们进行调整。
2018年9月26日 下午4:10 板凳
循环建立初始堆时，最后一个非叶子结点不是length/2-1吗，比如示例用length/2=7/2=3,即向HeapAdjust传递参数parent=3，那么child=7,显然不满足条件child<length;虽然最终结果不会出错，但这样就多循环了一次
2018年9月26日 下午4:49 1层
@示波器 非叶子结点是n/2啊。
2018年9月26日 下午7:18 地板
按照你代码上的函数给出的数组arr{6, 4, 8, 9, 2, 3, 1},length=7,那么HeapAdjust函数中参数parent传递的值不就是length/2==7/2=3，而arr[3]=9,9是叶子结点，arr[2]=8,8不应该才是最后一个非叶子结点 吗
2018年9月27日 上午8:28 1层
@示波器 哦哦，明白你的意思了，感谢。堆调整那里多调整一次，代码已更改。
2018年10月6日 下午10:15 4楼
在HeadSort函数中，每次进行最后一元素与第一元素交换后，C++版46行只是单一的从根节点往下进行了一次上浮调整，而不是从最后一个非叶子结点开始重新建立大根堆，这样做会出现问题吗；按照楼主前面说的“每次交换第一个和最后一个元素，输出最后一个元素（最大值），然后把剩下元素重新调整为大根堆。”，不是应该重新调整为大根堆吗，这里怎么只进行了一次从根节点往下的上浮调整
2018年10月6日 下午11:40 1层
@示波器 调整堆，就是进行一次这样的上浮调整就可以了啊。初始化堆的时候，需要进行length/2次的调整。
2019年3月5日 上午10:14 5楼
在python中， 初始化堆后list[9, 6, 8, 4, 2, 3, 1]，第一次交换后变为list[1, 6, 8, 4, 2, 3, 9]，那么在while循环里，child等于5时，满足child + 1< length 和 list[5] < list[6]，为什么child += 1这步不运行？
2019年3月5日 上午10:30 1层
@beo 观察到了，HeadAjust传递的length每次都会改变
2019年3月5日 上午11:38 2层
@beo Good~
2019年6月12日 下午9:05 6楼
博主的网站做的也太好看了吧！！！！讲解也很明白呀！！！感谢！！！
2019年6月13日 上午9:30 1层
@zdluffy 感谢支持～加油啦～
2020年9月10日 下午9:25 7楼
哎呀有点没太看懂，不过代码确实很清晰我再琢磨琢磨
2024年4月6日 下午1:35 8楼
来了