本篇文章帶給大家的內容是java中什麼是堆排序？堆排序介紹。有一定的參考價值，有需要的朋友可以參考一下，希望對你們有幫助。
堆排序介紹：
堆排序可以分成兩個階段。在堆的構造階段，我們將原始數組重新組織安排進一個堆中；然後在下沉排序階段，我們從堆中按順序取出所有元素並得到排序結果。
1.堆的構造，一個有效的方法是從右到左使用sink()下沉函數建構子堆。數組的每個位置都有一個子堆的根節點，sink()對於這些子堆也適用，如果一個節點的兩個子節點都已經是堆了，那麼在該節點上調用sink()方法可以把他們合併成一個堆。我們可以跳過大小為1的子堆，因為大小為1的不需要sink()也就是下沉操作，有關下沉和上浮操作可以參考我寫的優先隊列那篇。
2.堆的排序，我們透過第一步操作建構了一個堆，在這個堆中，根節點永遠是最大值的節點，所以我們把根節點的值與數組最後的值進行交換，在使用sink()下沉來維護堆的結構即可。
具體程式碼實作:
public class PQSort{
public static void main(String[] args){
int[] a = {9,1,7,5,3,9,12,56,21,45};
sort(a);
for(int i=0;i<a.length system.out.print public int for>=0;k--){
sink(a,k,N);
}
//通过不断把堆中最大值放到数组的后面来排序
while(N>0){
exch(a,0,N--);
sink(a,0,N);
}
}
//下沉函数
private static void sink(int[] a, int i, int n){
while(2*i+1a[j]) break;
exch(a,i,j);
i=j;
}
}
//交换函数
private static void exch(int[] a, int i, int j){
int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}</a.length>運行結果:
以上是java中什麼是堆排序？堆排序介紹的詳細內容。更多資訊請關注PHP中文網其他相關文章！
