堆排序： 特點 堆排序（HeapSort）是一樹形選擇排序。堆排序的特點是：在排序過程中，將R[l..n]看成是一棵完全二叉樹的順序存儲結構， 利用完全二叉樹中雙親結點和孩子結點之間的內在關系（參見二叉樹的順序存儲結構），在當前無序區中選擇關鍵字最大（或最小）的記錄 堆排序與直接選擇排序的區別直接選擇排序中，為了從R[1..n]中選出關鍵字最小的記錄，必須進行n-1次比較，然後在R[2..n]中選出關鍵字 最小的記錄，又需要做n-2次比較。事實上，後面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經做過，但由於前一趟排序時未保留 這些比較結果，所以後一趟排序時又重復執行了這些比較操作。 注：堆排序可通過樹形結構保存部分比較結果，可減少比較次數。 算法分析 堆排序的時間，主要由建立初始堆和反復重建堆這兩部分的時間開銷構成，它們均是通過調用Heap實現的。 堆排序的最壞時間復雜度為O(nlogn)。堆序的平均性能較接近於最壞性能。 由於建初始堆所需的比較次數較多，所以堆排序不適宜於記錄數較少的文件。 堆排序是就地排序，輔助空間為O(1）， 它是不穩定的排序方法。 實在如下：
/* Filename:myHeapsort.cpp Author: xiaobing E-mail: [email protected] Date: 2013-08-27 */ #include<iostream> #include<string> #include<algorithm> #include<cstdlib> #define N 10 using namespace std; void swap(int *a, int *b){ int temp = *a; *a = *b; *b = temp; } /* 堆排序實現 n個關鍵字序列Kl，K2，…，Kn稱為（Heap），當且僅當該序列滿足如下性質（簡稱為堆性質）： (1)ki<=k(2i）且ki<=k(2i+1)(1≤i≤ n），當然，這是小根堆，大根堆則換成>=號。 k(i）相當於二叉樹的非葉結點，K(2i）則是左孩子，k(2i+1）是右孩子 若將此序列所存儲的向量R[1..n]看做是一棵完全二叉樹的存儲結構，則堆實質上是滿足如下性質的完全二叉樹： 樹中任一非葉結點的關鍵字均不大於（或不小於）其左右孩子（若存在）結點的關鍵字。 實現原理： 1。開始時，需將數組建立為一個堆，使得其滿足所有的非葉節點的值都大於等於（或小於等於）其左右 孩子節點的值，這樣的效果使得第一個節點，即根節點總是最大的元素。 2.從最後一個數組元素開始與數組第一個元素交換數據，交換一次後，再創新建立堆，但堆的長度減1，直到 數組長度變為1為止，這樣就排序完成 注：使得每個非葉節點的值都大於等左右孩子節點的值，是實現由小到大排序 相反，是實現由大到小排序。 */ /* *@prama arr 待排序的數組 @prama i 待開始調整的位置 @prama length 調整的范圍，當然，開始時是數組長度，但後面會越來越小直到為1 * */ void heapAdjust(int arr[], int i, int length){ int temp, child; //定義了一個temp來存儲調整的值，child來指定該調整值的孩子位置 //緩存上應該調整的值 for(temp = arr[i]; 2 * i + 1 < length; i = child){ //孩子為左孩子 child = 2 * i + 1; //如果滿足child + 1 < length 這個是確定不會越界 //這樣就觀察左孩子與右孩子誰大，若右孩子大，則child 為右孩子，child + 1 if(child + 1 < length && arr[child + 1] > arr[child]){ child++; } //如果孩子節點比父節點大，因為剛才已經確定了arr[child]是左右孩子中的大著 //更新父節點為大值 if(arr[child] > temp){ arr[i] = arr[child]; } else { //如果父節點是大者，則已經調整好，所以退出循環 break; } //若更新後，則交換值，若沒有更新，則已經退出了，不能執行到此 arr[child] = temp; } } /* @prama arr 待排序的數組 @prama length 數組的長度 */ void heapsort(int arr[], int length){ int i; //實現第一步 /* 這裡從i = length / 2 -1開始調節，原理是： i = length /2 - 1是數組元素，以0為根，順序構造完全二叉樹時，最後一個非葉節點 因此，以該點開始調節，逐漸減i，把最後一排的元素的最大值都替換為其父節點倒數 第二排的值，逐漸減i，到了倒數第三排，然後把倒數第二排的最大值又替換為父節點 倒數第三排的值，以此類推，最終根元素的值就是最大的，當然，如果要從大到小排序 則可以讓根的值為最小值， 不明白時，可以把完全二叉樹畫出來看一下，就清晰了 */ for(i = length / 2 - 1; i >= 0; i--){ heapAdjust(arr, i, length); } //實現第二步 /* *這裡是從最後元素開始調整，不斷縮小范圍，直到第一個元素為止 */ for(i = length - 1;i > 0;i--){ //總是把第一個元素和後面的元素進行交換，因為第一個元素總是最大的(或最小的) swap(&arr[i], &arr[0]); //交換一次後，應該再調整一次，尋找其余的元素的最大值（或最小值）存在根為止，即0位置 heapAdjust(arr, 0, i - 1); } } void print(int arr[], int n){ int i; for(i = 0; i < n;i++){ cout<<arr[i]<<" "; } cout<<endl; } int main(){ int arr[N] = {213,354,45,123,4,6,57,7,8,56}; heapsort(arr, N); print(arr, N); return 0; }
