一,堆排序介紹
堆是一個優先級隊列,對於大頂堆而言,堆頂元素的權值最大。將 待排序的數組 建堆,然後不斷地刪除堆頂元素,就實現了排序。關於堆,參考:數據結構--堆的實現之深入分析 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)
此外,對於堆排序而言,數據的初始順序對它的復雜度沒有影響。不管數組初始時就是有序的還是逆序的,它都會先建堆,變成了堆序的性質。