堆排序的實現 · 程序算法藝術與實踐

### 堆排序（Heap Sort）堆排序（HeapSort）是一樹形選擇排序。堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系，在當前無序區中選擇關鍵字最大（或最小）的記錄.堆排序的最壞時間復雜度為O(nlogn)。堆序的平均性能較接近于最壞性能。由于建初始堆所需的比較次數較多，所以堆排序不適宜于記錄數較少的文件。堆排序是就地排序，輔助空間為O(1），它是不穩定的排序方法。如果需求是從很大的數據中選取特定的幾個最大活最小值，那么堆排序是最好的選擇。 ### 步驟堆排序的基本步驟就是： 1. 初始建堆. 1. 將堆頂元素與有序區的第一個元素交換. 1. 然后對堆頂元素開始調整堆，跳轉到2執行。直到全部有序。聲明：下面算法的實現中，數組的存儲位于data[1]-------data[n] 該算法中最核心的算法是堆的調整算法： ~~~ //堆調整 //data[],要排序的數組 target,要調整的元素位置 n,數組大小 void AdjustHeap(int data[],int target,int n){ int nChild; int nTemp; nTemp = data[target]; //暫存 while(target * 2 <= n){ nChild = target * 2; //nChild指向左孩子 if(nChild + 1 <= n && data[nChild] < data[nChild + 1]){ nChild++; //nChild指向關鍵字大的孩子（看是否有左孩子，若有，則左右孩子比較） } if(nTemp < data[nChild]){ //孩子節點比父節點大，則進行孩子節點移到父節點的位置 data[target] = data[nChild]; target = nChild; //再處理剛剛調整過的節點的字節點 } else break; } data[target] = nTemp; //最后將要調整的元素放到合適的位置 } ~~~ ### 整體實現代碼： ~~~ /******** * 堆排序算法 * 排序數組下標從1開始 */ #include <stdio.h> enum{MAX = 1000+1,}; int data[MAX]; static inline swap(int x,int y) {/* x ^= y; y ^= x; x ^= y; */ int tmp; tmp = data[x]; data[x] = data[y]; data[y] = tmp; } //堆調整 //data[],要排序的數組 //target,要調整的元素位置 //n,數組大小 void AdjustHeap(int data[],int target,int n){ int nChild; int nTemp; nTemp = data[target]; //暫存 while(target * 2 <= n) { nChild = target * 2; if(nChild + 1 <= n && data[nChild] < data[nChild + 1]){ nChild++; //nChild指向關鍵字大的孩子 } if(nTemp < data[nChild]) { data[target] = data[nChild]; target = nChild; //再處理剛剛調整過的節點的字節點 } else break; } data[target] = nTemp; //最后將要調整的元素放到合適的位置 } //堆排序算法 data，要排序的數組 n，數組大小 void HeapSort(int data[],int n){ int i; for(i = n/2;i > 0;--i){ AdjustHeap(data,i,n); } for(i = n;i > 1;--i) { swap(1,i); AdjustHeap(data,1,i - 1); } } int main() { freopen("random","r",stdin); freopen("oder","w",stdout); int i; for(i = 1;i <= MAX;++i) { scanf("%d",&data[i]); } //stderr("開始排序\n"); HeapSort(data,MAX); //stderr("排序結束\n"); for(i = 1;i <= MAX;++i) { printf("%d\n",data[i]); } return 0; } ~~~ **轉載請注明出處**：[http://blog.csdn.net/utimes/article/details/8759668](http://blog.csdn.net/utimes/article/details/8759668)