本文實例講述了C++實現堆排序算法的方法，相信對于大家學習數據結構與算法會起到一定的幫助作用。具體內容如下：
首先，由于堆排序算法說起來比較長，所以在這里單獨講一下。堆排序是一種樹形選擇排序方法，它的特點是：在排序過程中，將L[n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親節點和孩子節點之間的內在關系，在當前無序區中選擇關鍵字最大（或最小）的元素。
一、堆的定義
堆的定義如下：n個關鍵字序列L[n]成為堆，當且僅當該序列滿足：
①L(i) <= L(2i)且L(i) <= L(2i+1) 或者 ②L(i) >= L(2i)且L(i) >= L(2i+1) 其中i屬于[1, n/2]。
滿足第①種情況的堆稱為小根堆（小頂堆），滿足第②種情況的堆稱為大根堆（大頂堆）。在大根堆中，最大元素存放在根結點中，且對任一非根結點，它的值小于或等于其雙親結點值。小根堆則恰恰相反，小根堆的根結點存放的是最小元素。例如{16, 14, 10, 8, 7, 9, 3, 2}表示的大根堆：
二、構造初始堆
堆排序的關鍵就是構造初始堆。n個結點的完全二叉樹中，最后一個結點是第n/2（向下取整）個結點的孩子。所以構造初始堆的流程是：對第n/2（向下取整）個結點為根的子樹進行篩選（以大根堆為例，若根結點的關鍵字小于左右子女中關鍵字的較大者，則交換），使該子樹成為堆。之后向前依次對從n/2-1到1的各結點為根的子樹進行篩選，看該結點值是否大于其左右子結點的值，若不是，將左右子結點中較大值與之交換，交換后可能會破壞下一級的堆，于是繼續采用上述方法構造下一級的堆，直到以該結點為根的子樹構成堆為止。反復利用上述調整堆的方法建堆，直到根結點。
由于在數組中下標從0開始，所以在堆中i的左子結點為2*i+1，右子結點為2*i+2。下面是將某個結點i向下調整建堆的算法實現：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
void AdjustDown(ElementType A[], int i, int len) { ElementType temp = A[i]; // 暫存A[i] for(int largest=2*i+1; largest<len; largest=2*largest+1) { if(largest!=len-1 && A[largest+1]>A[largest]) ++largest; // 如果右子結點大 if(temp < A[largest]) { A[i] = A[largest]; i = largest; // 記錄交換后的位置 } else break; } A[i] = temp; // 被篩選結點的值放入最終位置 } |
建堆，從n/2（向下取整）到1依次對各結點向下調整，當然由于數組下標從0開始，所以：
|
1
2
3
4
5
|
void BuildMaxHeap(ElementType A[], int len) { for(int i=len/2-1; i>=0; --i) // 從i=n/2-1到0，反復調整堆 AdjustDown(A, i, len); } |
三、堆排序
構造初始堆成功以后，堆排序的思路就很簡單了：首先將存放在L[n]中的n個元素建成初始堆，由于堆本身的特點（以大根堆為例），堆頂元素就是最大值。輸出堆頂元素后，通常將堆底元素送入堆頂，此時根結點已不滿足大根堆的性質，堆被破壞。這時將堆頂元素向下調整使其繼續保持大根堆的性質，再輸出堆頂元素。如此重復，直到堆中僅剩下一個元素為止。算法實現如下：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
void HeapSort(ElementType A[], int n) { BuildMaxHeap(A, n); // 初始建堆 for(int i=n-1; i>0; --i) // n-1趟的交換和建堆過程 { // 輸出最大的堆頂元素（和堆底元素交換） A[0] = A[0]^A[i]; A[i] = A[0]^A[i]; A[0] = A[0]^A[i]; // 調整，把剩余的n-1個元素整理成堆 AdjustDown(A, 0, i); } } |
四、性能分析
時間復雜度：向下調整的時間與樹高有關，為O(h)。可以證明在元素個數為n的序列上建堆，其時間復雜度為O(n)。之后還有n-1次向下調整操作，每次調整的時間為O(h)，故在最好，最壞和平均情況下，堆排序的時間復雜度為O(nlogn)。
空間復雜度：僅使用了常數個輔助單元，空間復雜度為O(1)。
穩定性：不穩定。
