内部排序算法：堆排序

基本思想

• 堆的定义

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实现，代码如下所示：

01	public abstract class Sorter {

02	public abstract void sort(int[] array);

03

}

04

05	public class HeapSorter extends Sorter {

06

07	public void sort(int[] array) {

08	heapSort(array);

09

}

10

11

/**

12	* <p>堆排序方法

13	* <p>基于大根堆的堆排序方法

14

*/

15	private void heapSort(int[] array) {

16	Integer tmp; // 用于交换的暂存单元

17	buildHeap(array); // 执行初始建堆，并调整

18	for (int i = 0; i < array.length; i++) {

19	// 交换堆顶元素array[0]和堆中最后一个元素array[array.length-1-i]

20	tmp = array[0];

21	array[0] = array[array.length - 1 - i];

22	array[array.length - 1 - i] = tmp;

23	// 每次交换堆顶元素和堆中最后一个元素之后，都要对堆进行调整

24	adjustHeap(array, 0, array.length - 1 - i);

25

}

26

}

27

28

/**

29

* <p>

30

* 建堆方法

31

* <p>

32	* 调整堆中0~array.length/2个结点，保持堆的性质

33

*

34

*/

35	private void buildHeap(int[] array) {

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

37	int pos = (array.length - 1) / 2;

38	// 从该结点结点开始，执行建堆操作

39	for (int i = pos; i >= 0; i--) {

40	adjustHeap(array, i, array.length); // 在建堆过程中，及时调整堆中索引为i的结点

41

}

42

}

43

44

/**

45

* <p>

46

* 调整堆的方法

47

*

48	* @param s 待调整结点的索引

49	* @param m 待调整堆的结点的数量(亦即：排除叶子结点)

50

*/

51	private void adjustHeap(int[] array, int s, int m) {

52	Integer tmp = array[s]; // 当前待调整的结点

53	int i = 2 * s + 1; // 当前待调整结点的左孩子结点的索引(i+1为当前调整结点的右孩子结点的索引)

54	while (i < m) {

55	if (i + 1 < m && array[i] < array[i + 1]) { // 如果右孩子大于左孩子(找到比当前待调整结点大的孩子结点)

56	i = i + 1;

57

}

58	if (array[s] < array[i]) {

59	array[s] = array[i]; // 孩子结点大于当前待调整结点，将孩子结点放到当前待调整结点的位置上

60	s = i; // 重新设置待调整的下一个结点的索引

61	i = 2 * s + 1;

62	} else { // 如果当前待调整结点大于它的左右孩子，则不需要调整，直接退出

63

break;

64

}

65	array[s] = tmp; // 当前待调整的结点放到比其大的孩子结点位置上

66

}

67

}

68

}

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

01	class Sorter:

02

'''

03	Abstract sorter class, which provides shared methods being used by

04	subclasses.

05

'''

06	__metaclass__ = ABCMeta

07

08	@abstractmethod

09	def sort(self, array):

10

pass

11

12	class HeapSorter(Sorter):

13

'''

14	Heap sorter

15

'''

16	def sort(self, array):

17	length = len(array)

18	self.__heapify(array)

19

i = 0

20	while i<length:

21	array[0], array[length-1-i] = array[length-1-i], array[0]

22	self.__sift_down(array, 0, length-1-i)

23

i = i + 1

24

25	def __heapify(self, array):

26	length = len(array)

27	pos = (length-1) // 2

28

i = pos

29	while i>=0:

30	self.__sift_down(array, i, length)

31

i = i - 1

32

33	def __sift_down(self, array, s, m):

34	tmp = array[s]

35	i = 2 * s + 1

36	while i<m:

37	if i+1<m and array[i]<array[i+1]:

38

i = i + 1

39	if array[s]<array[i]:

40	array[s] = array[i]

41

s = i

42	i = 2 * s + 1

43

else:

44

break

45	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看做是一棵完全二叉树，这样数组每个索引位置上的元素都对应到二叉树中的结点，如图所示：

其中需要在这棵树中找到最后一个有孩子最大的一个结点的索引：
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）进行调整；

调整结点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，交换后如图所示：

继续对下一个结点（也就是array[8] = 55）进行调整；

调整结点array[7] = 37：

显然，不需要交换；

调整结点array[6] = 0：

调整结果如图所示：

调整结点array[5] = 9：

调整结果如图所示：

调整结点array[4] = 26：

调整结果如图所示：

调整结点array[3] = 76：

显然，不需要交换。

调整结点array[2] = 34：

调整结果如图所示：

调整结点array[1] = 12：

调整结果如图所示：

调整结点array[0] = 94：

显然，不需要交换。

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

第二步：第一次交换
将堆顶元素与最后一个元素交换，即array[0] = 94与最后一个元素array[19] = 49交换，如图所示：

此时，数组为：
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)。

• 排序稳定性

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