采用堆排序的方法去排序一個數組{47, 35, 26, 20, 18, 7, 13, 10}

數組對應堆的圖例，根節點大于左右孩子節點

分析：

1. 組建堆，第i個節點和其左右孩子分别對應第2*i 1和2*i 2下标的數據

2. 如何确定堆有幾層？如下

3. 數組的最後一個值得下标為n其父節點為i，所以存在關系n = 2*i 1 => i = (n-1)/2

4. 即第0~i個節點是有子節點，i 1~n個節點是葉子節點

5. 首次建堆處理，把樹處理成根節點大于或等于其左右孩子的樹

6. 首次建堆後的數據是大根堆，但是此時從上往下，從左往右并不是有序的

7. 然而，首次建堆不是有序的，但是此時堆頂元素肯定是最大的

8. 因此把堆頂元素和數組最後一個元素交換位置，然後剔除掉最後一個元素，重新建堆

9. 為此時，除了第一個元素，其他元素都是符合大根堆關系的，因此，從0開始建堆（不同于一開始的，以每一個小節點建堆，再逐步組裝起來）

10. 最後的堆頂元素是最大的，重複7、8步驟，直到全部元素處理完畢。

#include<iostream> using namespace std; class Heap { private: int arr[10] = {47, 35, 26, 20, 18, 7, 13, 10, 8, 6}; public: void show(); void sort(int n); void sortHeap(int k, int n); // 在當前節點中排序 }; void Heap::show() { for (int i = 0; i < 10; i ) { cout<<this->arr[i]<<" "; } cout<<endl; } // n 表示數組長度，k表示該根節點的下标 void Heap::sortHeap(int k, int n) { int i, j, temp; i = k; j = 2 * i 1; // 操作第k層和其孩子比較 while(j < n) { // 在數組邊界内, 比較左右孩子，較大的孩子與根節點比較 if (j < n-1 && this->arr[j] < arr[j 1]) j ; if (this->arr[i] > this->arr[j]) { break; } else { temp = this->arr[i]; this->arr[i] = this->arr[j]; this->arr[j] = temp; this->show(); // 交換後，後面可能存在大于改根節點的值，所以交換後的節點作為根節點，繼續比較，直到條件不成立 i = j; j = 2*i 1; } } } void Heap::sort(int n) { int i, temp; // 從後往前遍曆有根節點，最後一個根節點的下标n=2*i 1 => i = (n-1) / 2得到根節點 for (i = (n-1)/2; i >= 0; i--) { this->sortHeap(i, n); this->show(); } cout<<"---"<<endl; // 将堆頂的數值和最後一個未交換過的下标的值交換，得到的下标n-i是目前未處理的最大的數值 for (i = 1; i <= n-1; i ) { cout<<"堆頂"<<this->arr[i]<<endl; temp = this->arr[0]; this->arr[0] = this->arr[n - i]; this->arr[n-i] = temp; // 重新建隊，n-i個節點下标後已經是處理過的值，不需要在堆中處理 this->sortHeap(0, n-i); } this->show(); } int main() { Heap heap; // heap.show(); heap.sort(10); heap.show(); return 0; }

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!