一，堆排序介紹
堆是一個優先級隊列，對於大頂堆而言，堆頂元素的權值最大。將 待排序的數組 建堆，然後不斷地刪除堆頂元素，就實現了排序。關於堆，參考：數據結構--堆的實現之深入分析 http://www.linuxidc.com/Linux/2016-05/131796.htm
下面的堆排序算法將數組中的元素從小到大排序，用大頂堆來實現。
二，堆排序算法分析
現給定了一維數組，需要將數組中的元素使用堆排序。首先，得創建一個堆，可以在這個給定的一維數組上建堆。 對N個元素 建堆的時間復雜度為O(N)
堆排序具體的細節實現有兩種方式：一種方式是將堆頂元素刪除後，放到一個輔助數組中，然後進行堆調整使之成為一個新。繼續刪除堆頂元素，直至將堆中所有的元素都出堆，此時排序完成。這種方式需要一個額外的輔助空間O(N)
另一種方式是：將每次刪除的堆頂元素放到數組的末尾。因為，對於堆的基本操作 delMin/delMax 而言（delMin針對的是小頂堆，delMax針對的是大頂堆，原理一樣）是將堆中的最後一個元素替換堆頂元素，然後向下進行堆調整。因此，可以利用這個特點將每次刪除的堆頂元素保存在數組末尾，當所有的元素都出堆後，數組就排好序了。這種方式不需要額外的輔助空間，空間復雜度為O(1)
三，堆排序算法實現
public class HeapSort {
public static <T extends Comparable<? super T>> void heapSort(T[] arr){
//build heap
for(int i = arr.length/2 - 1; i >= 0; i--)
percDown(arr, i, arr.length);
for(int i = arr.length - 1; i >= 0; i--)
{
swapReference(arr, 0, i);//delete Max
percDown(arr, 0, i);// 從根開始向下堆調整
}
}
private static <T extends Comparable<? super T>> void swapReference(T[] arr, int from, int to){
T tmp;
tmp = arr[from];
arr[from] = arr[to];
arr[to] = tmp;
}
//求解 i 的左孩子
private static int leftChild(int i){
return 2*i + 1;
}
/**
*
* @param arr 存儲堆的一維數組
* @param i 從 i 位置開始進行向下堆調整
* @param n 堆中元素的個數(不是數組的長度)
*/
private static <T extends Comparable<? super T>> void percDown(T[] arr, int i, int n){
int child;
T tmp;//保存當前待調整的結點，當找到了合適的位置後，需要將之放入到合適位置，以保持堆序性質
for(tmp = arr[i]; leftChild(i) < n; i = child)
{
child = leftChild(i);
if(child != n-1 && arr[child].compareTo(arr[child+1]) < 0)
child++;//右孩子更大
if(tmp.compareTo(arr[child]) < 0)
arr[i] = arr[child];//父節點下移
else
break;//父節點比左右孩子都大時,不需要再向下移動了
}
arr[i] = tmp;//將節點放入合適的位置
}
//for test purpose
public static void main(String[] args) {
Integer[] arr = {31,41,59,26,53,58,97};
heapSort(arr);
for (Integer i : arr) {
System.out.print(i + " ");
}
}
}
有幾個細節地方解釋一下：
①在第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)
此外，對於堆排序而言，數據的初始順序對它的復雜度沒有影響。不管數組初始時就是有序的還是逆序的，它都會先建堆，變成了堆序的性質。
