算法思想
堆排序利用了最大堆（或小根堆）堆頂記錄的關鍵字最大（或最小）這一特征，使得在當前無序區中選取最大（或最小）關鍵字的記錄變得簡單。
1.用最大堆排序的基本思想
（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]調整為堆。
……
直到無序區只有一個元素為止。
2.最大堆排序算法的基本操作：
（1）建堆，建堆是不斷調整堆的過程，從len/2處開始調整，一直到第一個節點，此處len是堆中元素的個數。建堆的過程是線性的過程，從len/2到0處一直調用調整堆的過程，相當于o(h1)+o(h2)…+o(hlen/2) 其中h表示節點的深度，len/2表示節點的個數，這是一個求和的過程，結果是線性的O(n)。
（2）調整堆：調整堆在構建堆的過程中會用到，而且在堆排序過程中也會用到。利用的思想是比較節點i和它的孩子節點left(i),right(i)，選出三者最大(或者最小)者，如果最大（小）值不是節點i而是它的一個孩子節點，那邊交互節點i和該節點，然后再調用調整堆過程，這是一個遞歸的過程。調整堆的過程時間復雜度與堆的深度有關系，是lgn的操作，因為是沿著深度方向進行調整的。
（3）堆排序：堆排序是利用上面的兩個過程來進行的。首先是根據元素構建堆。然后將堆的根節點取出(一般是與最后一個節點進行交換)，將前面len-1個節點繼續進行堆調整的過程，然后再將根節點取出，這樣一直到所有節點都取出。堆排序過程的時間復雜度是O(nlgn)。因為建堆的時間復雜度是O(n)（調用一次）；調整堆的時間復雜度是lgn，調用了n-1次，所以堆排序的時間復雜度是O(nlgn)[2]
注意
（1）只需做n-1趟排序，選出較大的n-1個關鍵字即可以使得文件遞增有序。
（2）用小根堆排序與利用最大堆類似，只不過其排序結果是遞減有序的。堆排序和直接選擇排序相反：在任何時刻堆排序中無序區總是在有序區之前，且有序區是在原向量的尾部由后往前逐步擴大至整個向量為止
Swift示例
（1）基于最大堆實現升序排序
|
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
|
func initHeap(inout a: [Int]) { for var i = (a.count - 1) / 2; i >= 0; --i { adjustMaxHeap(&a, len: a.count, parentNodeIndex: i) }} func adjustMaxHeap(inout a: [Int], len: Int, parentNodeIndex: Int) { // 如果len <= 0，說明已經無序區已經縮小到0 guard len > 1 else { return } // 父結點的左、右孩子的索引 let leftChildIndex = 2 * parentNodeIndex + 1 // 如果連左孩子都沒有， 一定沒有右孩子，說明已經不用再往下了 guard leftChildIndex < len else { return } let rightChildIndex = 2 * parentNodeIndex + 2 // 用于記錄需要與父結點交換的孩子的索引 var targetIndex = -1 // 若沒有右孩子，但有左孩子，只能選擇左孩子 if rightChildIndex > len { targetIndex = leftChildIndex } else { // 左、右孩子都有，則需要找出最大的一個 targetIndex = a[leftChildIndex] > a[rightChildIndex] ? leftChildIndex : rightChildIndex } // 只有孩子比父結點還要大，再需要交換 if a[targetIndex] > a[parentNodeIndex] { let temp = a[targetIndex] a[targetIndex] = a[parentNodeIndex] a[parentNodeIndex] = temp // 由于交換后，可能會破壞掉新的子樹堆的性質，因此需要調整以a[targetIndex]為父結點的子樹，使之滿足堆的性質 adjustMaxHeap(&a, len: len, parentNodeIndex: targetIndex) }} func maxHeapSort(inout a: [Int]) { guard a.count > 1 else { return } initHeap(&a) for var i = a.count - 1; i > 0; --i { // 每一趟都將堆頂交換到指定范圍內的最后一個位置 if a[0] > a[i] { let temp = a[0] a[0] = a[i] a[i] = temp } print(a) print(i - 1) // 有序區長度+1，而無序區長度-1，繼續縮小無序區，所以i-1 // 堆頂永遠是在0號位置，所以父結點調整從堆頂開始就可以了 adjustMaxHeap(&a, len: i - 1, parentNodeIndex: 0) print(a) }} |
（2）基于最小堆降序排序
|
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
|
func initHeap(inout a: [Int]) { for var i = (a.count - 1) / 2; i >= 0; --i { adjustMinHeap(&a, len: a.count, parentNodeIndex: i) }} func adjustMinHeap(inout a: [Int], len: Int, parentNodeIndex: Int) { // 如果len <= 0，說明已經無序區已經縮小到0 guard len > 1 else { return } // 父結點的左、右孩子的索引 let leftChildIndex = 2 * parentNodeIndex + 1 // 如果連左孩子都沒有， 一定沒有右孩子，說明已經不用再往下了 guard leftChildIndex < len else { return } let rightChildIndex = 2 * parentNodeIndex + 2 // 用于記錄需要與父結點交換的孩子的索引 var targetIndex = -1 // 若沒有右孩子，但有左孩子，只能選擇左孩子 if rightChildIndex > len { targetIndex = leftChildIndex } else { // 左、右孩子都有，則需要找出最大的一個 targetIndex = a[leftChildIndex] < a[rightChildIndex] ? leftChildIndex : rightChildIndex } // 只有孩子比父結點還要大，再需要交換 if a[targetIndex] < a[parentNodeIndex] { let temp = a[targetIndex] a[targetIndex] = a[parentNodeIndex] a[parentNodeIndex] = temp // 由于交換后，可能會破壞掉新的子樹堆的性質，因此需要調整以a[targetIndex]為父結點的子樹，使之滿足堆的性質 adjustMinHeap(&a, len: len, parentNodeIndex: targetIndex) }} func minHeapSort(inout a: [Int]) { guard a.count > 1 else { return } initHeap(&a) for var i = a.count - 1; i > 0; --i { // 每一趟都將堆頂交換到指定范圍內的最后一個位置 if a[0] < a[i] { let temp = a[0] a[0] = a[i] a[i] = temp } else { return // 可以直接退出了，因為已經全部有序了 } // 有序區長度+1，而無序區長度-1，繼續縮小無序區，所以i-1 // 堆頂永遠是在0號位置，所以父結點調整從堆頂開始就可以了 adjustMinHeap(&a, len: i - 1, parentNodeIndex: 0) }} |
測試：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
|
var arr = [5, 3, 8, 6, 4]//var arr = [89,-7,999,-89,7,0,-888,7,-7]maxHeapSort(&arr) print(arr) // 打印日志如下：[4, 6, 5, 3, 8]3[6, 4, 5, 3, 8] [3, 4, 5, 6, 8]2[5, 4, 3, 6, 8] [3, 4, 5, 6, 8]1[3, 4, 5, 6, 8] [3, 4, 5, 6, 8]0[3, 4, 5, 6, 8] [3, 4, 5, 6, 8] |
