内部排序算法：堆排序

一时失言乱红尘 2022-05-26 12:15 167阅读 0赞

本文是转载文章，文章的来源：简单之美  
博主：Yanjun  
文章：内部排序算法：堆排序  
博文地址：http://shiyanjun.cn/archives/802.html

基本思想

*  堆的定义

n个关键字序列kl，k2，…，kn称为堆，当且仅当该序列满足如下性质之一（简称堆性质）：

1.  ki≤k2i且ki≤k2i+1 或
2.  ki≥k2i且ki≥k2i+1（1≤i≤FLOOR(n/2)）

若将此序列所存储的向量R\[1..n\]看做是一棵完全二叉树的存储结构，则堆实质上是满足如下性质的完全二叉树：树中任一非叶结点的关键字均不大于（或不小于）其左右孩子（若 存在）结点的关键字。

*  小根堆：根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最小的。
 *  大根堆：根结点（亦称为堆顶）的关键字是堆里所有结点关键字中最大的。

我们可以选择大根堆或者小根堆中的任意一个来进行排序。

*  排序思想

用大根堆排序的基本思想：

1.  先将初始文件R\[1..n\]建成一个大根堆，此堆为初始的无序区。
2.  再将关键字最大的记录R\[1\]（即堆顶）和无序区的最后一个记录R\[n\]交换，由此得 到新的无序区R\[1..n-1\]和有序区R\[n\]，且满足R\[1..n-1\].keys≤R\[n\].key。
3.  由于交换后新的根R\[1\]可能违反堆性质，故应将当前无序区R\[1..n-1\]调整为堆。 然后再次将R\[1..n-1\]中关键字最大的记录R\[1\]和该区间的最后一个记录R\[n-1\]交换，由 此得到新的无序区R\[1..n-2\]和有序区R\[n-1..n\]，且仍满足关系 R\[1..n-2\].keys≤R\[n-1..n\].keys，同样要将R\[1..n-2\]调整为堆。

算法实现

堆排序算法，Java实现，代码如下所示：

public abstract class Sorter {
 public abstract void sort(int[] array);
 }
 
 public class HeapSorter extends Sorter {
 
 public void sort(int[] array) {
 heapSort(array);
 }
 
 /**
 * 堆排序方法
 * 基于大根堆的堆排序方法
 */
 private void heapSort(int[] array) {
 Integer tmp; // 用于交换的暂存单元
 buildHeap(array); // 执行初始建堆，并调整
 for (int i = 0; i < array.length; i++) {
 // 交换堆顶元素array[0]和堆中最后一个元素array[array.length-1-i]
 tmp = array[0];
 array[0] = array[array.length - 1 - i];
 array[array.length - 1 - i] = tmp;
 // 每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整
 adjustHeap(array, 0, array.length - 1 - i);
 }
 }
 
 /**
 * 
 * 建堆方法
 * 
 * 调整堆中0~array.length/2个结点，保持堆的性质
 *
 */
 private void buildHeap(int[] array) {
 // 求出当前堆中最后一个存在孩子结点的索引
 int pos = (array.length - 1) / 2;
 // 从该结点结点开始，执行建堆操作
 for (int i = pos; i >= 0; i--) {
 adjustHeap(array, i, array.length); // 在建堆过程中，及时调整堆中索引为i的结点
 }
 }
 
 /**
 * 
 * 调整堆的方法
 *
 * @param s 待调整结点的索引
 * @param m 待调整堆的结点的数量(亦即：排除叶子结点)
 */
 private void adjustHeap(int[] array, int s, int m) {
 Integer tmp = array[s]; // 当前待调整的结点
 int i = 2 * s + 1; // 当前待调整结点的左孩子结点的索引(i+1为当前调整结点的右孩子结点的索引)
 while (i < m) {
 if (i + 1 < m && array[i] < array[i + 1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)
 i = i + 1;
 }
 if (array[s] < array[i]) {
 array[s] = array[i]; // 孩子结点大于当前待调整结点，将孩子结点放到当前待调整结点的位置上
 s = i; // 重新设置待调整的下一个结点的索引
 i = 2 * s + 1;
 } else { // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出
 break;
 }
 array[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上
 }
 }
 }

堆排序算法，Python实现，代码如下所示：

class Sorter:
 '''
 Abstract sorter class, which provides shared methods being used by
 subclasses.
 '''
 __metaclass__ = ABCMeta
 
 @abstractmethod 
 def sort(self, array):
 pass
 
 class HeapSorter(Sorter):
 '''
 Heap sorter
 ''' 
 def sort(self, array):
 length = len(array)
 self.__heapify(array)
 i = 0
 while i<length:
 array[0], array[length-1-i] = array[length-1-i], array[0]
 self.__sift_down(array, 0, length-1-i) 
 i = i + 1
 
 def __heapify(self, array):
 length = len(array)
 pos = (length-1) // 2
 i = pos
 while i>=0:
 self.__sift_down(array, i, length)
 i = i - 1
 
 def __sift_down(self, array, s, m):
 tmp = array[s]
 i = 2 * s + 1
 while i<m:
 if i+1<m and array[i]<array[i+1]:
 i = i + 1
 if array[s]<array[i]:
 array[s] = array[i]
 s = i
 i = 2 * s + 1
 else:
 break
 array[s] = tmp

排序过程

假设待排序数组为array = \{94,12,34,76,26,9,0,37,55,76,37,5,68,83,90,37,12,65,76,49\}，数组大小为20。

第一步：初始建堆  
首先执行的初始建堆（在建堆的过程中需要调整堆）。过程如下：

*  求出当前堆中最后一个存在孩子结点的索引

这里，把数组array看做是一棵完全二叉树，这样数组每个索引位置上的元素都对应到二叉树中的结点，如图所示：  
![heapsort][]  
其中需要在这棵树中找到最后一个有孩子最大的一个结点的索引：  
pos = (array.length-1)/2 = (20-1)/2 = 9  
也就是索引为9的array\[9\] = 76，由后至前层次遍历，从array\[9\]一直到array\[0\]，对初始堆进行调整。

*  对初始堆进行调整

1. 调整结点array\[9\] = 76：
 
 先比较array\[9\] = 76的左右孩子：s = 9，i = 2\*s+1 = 2\*9 + 1 = 19，而i+1 = 19 + 1 = 20 > m = array.length-1 = 20 -1 = 19(array\[9\] = 76没有右孩子)，只需要将array\[9\] = 76与array\[i\] = array\[19\] = 49比较，因为array\[9\] = 76>array\[i\] = array\[19\] = 49，则不需要交换array\[9\] = 76与array\[i\] = array\[19\] = 49，继续对下一个结点（也就是array\[8\] = 55）进行调整；
2. 调整结点array\[8\] = 55：
 
 先比较array\[8\] = 55的左右孩子：s = 8，i = 2\*s+1 = 2\*8 + 1 = 17,，而i+1 = 17 + 1 = 18 < m = array.length-1 = 20-1 = 19(array\[8\] = 55存在右孩子)，左孩子array\[i\] = array\[17\] = 65小于右孩子array\[i+1\] = array\[18\] = 76，只需要将array\[8\] = 76与右孩子array\[i+1\] = array\[18\] = 76比较，因为array\[8\] = 55<array\[i+1\] = array\[18\] = 76，则需要交换array\[8\] = 55与array\[i+1\] = array\[18\] = 76，交换后如图所示： 
 ![heapsort-1][] 
 继续对下一个结点（也就是array\[8\] = 55）进行调整；
3. 调整结点array\[7\] = 37：
 
 显然，不需要交换；
4. 调整结点array\[6\] = 0：
 
 调整结果如图所示： 
 ![heapsort-2][]
5. 调整结点array\[5\] = 9：
 
 调整结果如图所示： 
 ![heapsort-3][]
6. 调整结点array\[4\] = 26：
 
 调整结果如图所示： 
 ![heapsort-4][]
7. 调整结点array\[3\] = 76：
 
 显然，不需要交换。
8. 调整结点array\[2\] = 34：
 
 调整结果如图所示： 
 ![heapsort-5][]
9. 调整结点array\[1\] = 12：
 
 调整结果如图所示： 
 ![heapsort-6][]
10. 调整结点array\[0\] = 94：
 
 显然，不需要交换。

至此，对初始堆的调整完成。

第二步：第一次交换  
将堆顶元素与最后一个元素交换，即array\[0\] = 94与最后一个元素array\[19\] = 49交换，如图所示：  
![heapsort-7][]  
此时，数组为：  
array = \{49,76,90,12,76,68,34,37,76,26,37,5,9,83,0,37,12,65,55,94\}  
数组中最大的元素被交换到了数组的末尾，也就是array\[19\] = 94是最终排好序的固定位置。

第三步：调整堆  
过程同前面类似。  
……  
最后经过堆排序得到有序的数组。

算法分析

*  时间复杂度

堆排序的时间，主要由建立初始堆和反复重建堆这两部分的时间开销构成。  
堆排序的最坏时间复杂度为O(nlgn)。堆排序的平均性能较接近于最坏性能。由于建初始堆所需的比较次数较多，所以堆排序不适宜于记录数较少的文件。

*  空间复杂度

堆排序过程中，需要调整堆，交换待排序记录需要一个临时存储单元，所以空间复杂度为O(1)。

*  排序稳定性

堆排序是就地排序，它是不稳定的排序方法。

[![Creative Commons License][]][Creative Commons License 1]

本文基于[署名-非商业性使用-相同方式共享 4.0][-_-_ 4.0]许可协议发布，欢迎转载、使用、重新发布，但务必保留文章署名[时延军][Link 1]（包含链接：http://shiyanjun.cn），不得用于商业目的，基于本文修改后的作品务必以相同的许可发布。如有任何疑问，请与我[联系][Link 2]。

[heapsort]: http://shiyanjuncn.b0.upaiyun.com/wp-content/uploads/2014/03/heapsort.png
[heapsort-1]: http://shiyanjuncn.b0.upaiyun.com/wp-content/uploads/2014/03/heapsort-1.png
[heapsort-2]: http://shiyanjuncn.b0.upaiyun.com/wp-content/uploads/2014/03/heapsort-2.png
[heapsort-3]: http://shiyanjuncn.b0.upaiyun.com/wp-content/uploads/2014/03/heapsort-3.png
[heapsort-4]: http://shiyanjuncn.b0.upaiyun.com/wp-content/uploads/2014/03/heapsort-4.png
[heapsort-5]: http://shiyanjuncn.b0.upaiyun.com/wp-content/uploads/2014/03/heapsort-5.png
[heapsort-6]: http://shiyanjuncn.b0.upaiyun.com/wp-content/uploads/2014/03/heapsort-6.png
[heapsort-7]: http://shiyanjuncn.b0.upaiyun.com/wp-content/uploads/2014/03/heapsort-7.png
[Creative Commons License]: /images/20220526/f412c868c8234e49a0c85ace494d02bd.png
[Creative Commons License 1]: http://creativecommons.org/licenses/by-nc-sa/4.0
[-_-_ 4.0]: http://creativecommons.org/licenses/by-nc-sa/4.0/deed.zh
[Link 1]: http://shiyanjun.cn/
[Link 2]: mailto:i@shiyanjun.cn