堆排序的概念:
首先,我們先要理解堆的定義,
堆定義:n個關鍵字序列K1,K2,...,Kn稱為(Heap),當且僅當該序列滿足如下性質(簡稱:堆性質):
(1)k(i)<=k(2i) 且 k(i)<=k(2i+i) (1<=i<=n/2),當然,這是最小根堆,
(2)k(i)>=k(2i) 且 k(i)>=k(2i+i) (1<=i<=n/2),大根堆則換成>=號。
k(i)相當于二叉樹的非葉結點,k(2i)則是左孩子,k(2k+1)是右孩子
若將此序列所存儲的向量R[1...n]看做是一棵完全二叉樹的存儲結構,則堆實際上是滿足如下性質的完全二叉樹:
樹中任一非葉結點的關鍵字均不大于(或不小于)其左右孩子(若存在)結點的關鍵字。
下面舉例來具體說明什么是堆,
例:關鍵字序列(10,15,56,25,30,70)和(70,56,30,25,15,10)分別滿足性質1和性質2,故它們均是堆,其對應的完全二叉樹分別如小根堆實例和大根堆示例所示。
?
?
那么堆排序則是利用了大根堆(或)小根堆堆頂記錄的關鍵字最大(或最小)這一特征,使得在當前的無序區中選取
最大(或最小)關鍵字的記錄變得簡單。
我們想想看,如果是大根堆的話,那么它的最大根肯定是是里面的最大值,如果我們將其取走,
將剩下的數值在重新排列成堆,那么,它現在的頂根肯定又是最大值,
循環下去的話,我們會把一個個的最大值都給拆去出來,那么它們的排列順序,肯定是由大到小的
這樣,我們就完成了堆排序。
下面給出堆排序的C版代碼:
?
void HeadSort(SqList *L){ int i; for(i=L->length/2;i>0;i--){ HeapAdjust(L,i,L->length); } for(i=L->length;i>1;i--){ swap(L,1,i); HeadAdjust(L,1,i-1); } } void HeapAdjust(SqList *L,int s,int m){ int temp,j; temp = L->r[s]; for(j=2*s;j<=m;j*=2){ if(j<m&&L->r[j]<L->r[j+1]){ ++j; } if(temp>=L->r[j]){ break; } L->r[s] = L->r[j]; s=j; } L->r[s] = temp; }?
上面的代碼中,首先我們要無序的數值進行一次堆排序,然后,將最大數值和末尾的數值交換,
并且讓需要排序的數據長度減1,這樣,剩下的數據再次進行排序,然后,每次結束后,都首末相調,長度減1,
最終我們得到的結果,肯定是由小到大的順序表。
其中最令我們關注的應該是堆調整的算法了。
在HeapAdjust 方法中,我們傳入了數組的引用,需要調整的非葉節點的最大值,和數組的最大長度。
其中s是非葉節點的最大值,它是根據數組的長度/2取整的來的。
我們想想看,如果是9個數值,那么如果按照堆排序的話,肯定是頂根節點是一個數值,下面兩個子節點,
而節點又有節點,所以我們我們按從上之下的邏輯結構排,它們的個數肯定是1-2-4-2,
就如同上面的圖片一樣,那么需要調整的節點數肯定就是上面的非葉子節點了。一共有4個,也就是數組長度的1半了。
我們以頂根的下標為1,那么如果傳入s的初始值應該就是非葉子節點的最大下表了。
首先,我們把該下標所對應的值保存為臨時變量
然后取得這個節點的它的孩子節點,如果孩子節點的長度小于數組的最大長度,并且它的左孩子節點小于右孩子節點
則存儲孩子節點的j下標+1,這里,我們的目的就是要獲得孩子節點中的最大值的下標。
然后,用中間變量,也就是它們的父節點,與最大的孩子節點進行比較,
如果父節點大于孩子節點,則跳出循環,
但是如果小于呢?這是我們要將最大的孩子節點升級成為父節點,就是將孩子節點的值賦值給父節點。
并且將要s下標指向j,也就是最大孩子節點的初始位置,
這時j乘以2,j是當時最大的孩子,我們要繼續找,是否,以它為父節點,它的孩子有比臨時變量大的。
如果我們找到,則將孩子的值賦值給父節點r[s] = r[j] ,因為通過上次的循環,此時的s指向上次的最大孩子節點。
所以,再次賦值,就是將孩子的最大孩子節點賦值給父節點。
然后,在將j指向最大還是節點。
知道循環結束。
我們用中間變量替換最大孩子節點所在的值,至此,對堆的調整結束,它的根是目前最大的數值
?
后面的循環中,我們指明需要調整的其實位置是頂層位置,因為是收尾交換,其它數據的順序就不要動了。
當循環結束之后,則完成了堆排序
?
?
下面給出java版的實現:
?
package com.fortune.test; /** * Created with IntelliJ IDEA. * User: liupeng * Date: 12-7-10 * Time: 下午5:27 */ public class HeapSortTest { public static int[] head = new int[]{50, 10, 90, 30, 70, 40, 80, 60, 20}; public static void main(String args[]) { int temp; int i; for (i = head.length / 2 - 1; i >= 0; i--) { HeapAdjust(i, head.length - 1); } for (i = head.length - 1; i > 0; i--) { temp = head[0]; head[0] = head[i]; head[i] = temp; HeapAdjust(0, i - 1); } for (int j = 0; j < head.length; j++) { System.out.print(head[j] + " "); } } public static void HeapAdjust(int start, int length) { int temp, j; temp = head[start]; for (j = 2 * start + 1; j <= length; j = j * 2 + 1) { if ((j < length) && (head[j] < head[j + 1])) { ++j; } if (temp >= head[j]) { break; } head[start] = head[j]; start = j; } head[start] = temp; } }?
更多文章、技術交流、商務合作、聯系博主
微信掃碼或搜索:z360901061

微信掃一掃加我為好友
QQ號聯系: 360901061
您的支持是博主寫作最大的動力,如果您喜歡我的文章,感覺我的文章對您有幫助,請用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元
