排序算法總結之堆排序

一，堆排序介紹

堆是一個優先級隊列，對于大頂堆而言，堆頂元素的權值最大。将 待排序的數組 建堆，然後不斷地删除堆頂元素，就實作了排序。關于堆，參考：資料結構--堆的實作之深入分析

下面的堆排序算法将數組中的元素從小到大排序，用大頂堆來實作。

二，堆排序算法分析

 現給定了一維數組，需要将數組中的元素使用堆排序。首先，得建立一個堆，可以在這個給定的一維數組上建堆。 對N個元素 建堆的時間複雜度為O(N)

堆排序具體的細節實作有兩種方式：一種方式是将堆頂元素删除後，放到一個輔助數組中，然後進行堆調整使之成為一個新堆。接下來，繼續删除堆頂元素，直至将堆中所有的元素都出堆，此時排序完成。這種方式需要一個額外的輔助空間O(N)

另一種方式是：将每次删除的堆頂元素放到數組的末尾。因為，對于堆的基本操作 delMin/delMax 而言（delMin針對的是小頂堆，delMax針對的是大頂堆，原理一樣）是将堆中的最後一個元素替換堆頂元素，然後向下進行堆調整。是以，可以利用這個特點将每次删除的堆頂元素儲存在數組末尾，當所有的元素都出堆後，數組就排好序了。這種方式不需要額外的輔助空間，空間複雜度為O(1)

三，堆排序算法實作

1 public class HeapSort {
 2     
 3     public static <T extends Comparable<? super T>> void heapSort(T[] arr){
 4         //build heap
 5         for(int i = arr.length/2 - 1; i >= 0; i--)
 6             percDown(arr, i, arr.length);
 7         
 8         
 9         for(int i = arr.length - 1; i >= 0; i--)
10         {
11             swapReference(arr, 0, i);//delete Max
12             
13             percDown(arr, 0, i);// 從根開始向下堆調整
14         }
15     }
16     
17     private static <T extends Comparable<? super T>> void swapReference(T[] arr, int from, int to){
18         T tmp;
19         tmp = arr[from];
20         arr[from] = arr[to];
21         arr[to] = tmp;
22     }
23     
24     //求解 i 的左孩子
25     private static int leftChild(int i){
26         return 2*i + 1;
27     }
28     
29     /**
30      * 
31      * @param arr 存儲堆的一維數組
32      * @param i 從 i 位置開始進行向下堆調整
33      * @param n 堆中元素的個數(不是數組的長度)
34      */
35     private static <T extends Comparable<? super T>> void percDown(T[] arr, int i, int n){
36         int child;
37         T tmp;//儲存目前待調整的結點，當找到了合适的位置後，需要将之放入到合适位置，以保持堆序性質
38         
39         for(tmp = arr[i];  leftChild(i) < n; i = child)
40         {
41             child = leftChild(i);
42             if(child != n-1 && arr[child].compareTo(arr[child+1]) < 0)
43                 child++;//右孩子更大
44             if(tmp.compareTo(arr[child]) < 0)
45                 arr[i] = arr[child];//父節點下移
46             else
47                 break;//父節點比左右孩子都大時,不需要再向下移動了
48         }
49         arr[i] = tmp;//将節點放入合适的位置
50     }
51     
52     //for test purpose
53     public static void main(String[] args) {
54         Integer[] arr = {31,41,59,26,53,58,97};
55         heapSort(arr);
56         for (Integer i : arr) {
57             System.out.print(i + " ");
58         }
59     }
60 }      

有幾個細節地方解釋一下：

①在第3行的heapSort方法中，第5-6行是建堆操作，因為數組中的元素是從下标0開始存儲的，故最後一個非葉子結點的下标為：arr.length/2 - 1

②第9-14行是進行堆排序的操作。swapReference方法相當于删除堆頂元素，因為它把堆頂元素交換到數組的末尾去了，此時堆頂元素不再是最大值（大頂堆)。删除了堆頂元素之後，就要進行堆調整以保持堆序性質，故percDown方法 完成向下進行堆調整的功能。

③在堆調整的過程中，需要求解某個結點的左 右孩子結點的位置。故有一個leftChild方法用來求解左孩子的位置（注意元素是從數組下标0開始存儲的）

④percDown方法實作向下的堆調整功能。第37行  tmp 變量 儲存目前待調整的結點，當找到了合适的位置後，需要将之放入到合适位置，以保持堆序性質。對于建堆而言，待調整的結點是從 非葉結點 開始，直至根的那些結點。對于删除堆頂元素而言，則總是從堆頂元素起開始調整（待調整的結點是根）

⑤第39行的for循環實作得非常巧妙，首先tmp儲存目前待調整的結點 arr[i]，然後判斷 arr[i] 是否有左孩子，如果有左孩子的話，又在第42行的if語句中判斷它是否還有右孩子(child != n-1)，然後左右孩子進行比較，child記錄下權值大的那個孩子。

⑥第44-45行的if語句完成的功能是：将權值大的孩子與父結點比較，如果父結點的權值小，則需要将那個較大的孩子上移到父結點的位置（也相當于父結點下移到孩子的位置）

如果父結點的權值大，已經找到了合适的位置了。說明不需要再進行堆調整了，執行else break;

⑦第49行，就待調整的結點入到到合适的位置i處。整個過程并沒有用交換操作，而是用的是指派操作來隐式地實作了交換操作完成的功能，這是一個優化。

四，堆排序算法複雜度分析

對N個元素建堆的時間複雜度為O(N)，删除堆頂元素的時間複雜度為O(logN)，盡管随着元素的不斷删除，堆的排程越來越小，但是總的而言，删除堆所有元素的時間複雜度為O(NlogN)

故堆排序的時間複雜度為O(NlogN)，空間複雜度為O(1)

其實，堆排序是一個非常穩定的算法，最壞和平均情況下的時間複雜度都為O(NlogN)

此外，對于堆排序而言，資料的初始順序對它的複雜度沒有影響。不管數組初始時就是有序的還是逆序的，它都會先建堆，變成了堆序的性質。

五，參考資料

排序算法總結之插入排序

 排序算法總結之快速排序

排序算法總結之歸并排序

各種排序算法的總結