堆排序的概念：

首先，我們先要理解堆的定義，

堆定義：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;
    }
}

  

?

排序 - 堆排序