堆排序的概念:
首先,我們先要理解堆的定義,
堆定義: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元等您想捐的金額吧,狠狠點擊下面給點支持吧,站長非常感激您!手機微信長按不能支付解決辦法:請將微信支付二維碼保存到相冊,切換到微信,然后點擊微信右上角掃一掃功能,選擇支付二維碼完成支付。
【本文對您有幫助就好】元

