java的堆排序是什么意思？

本篇文章給大家?guī)淼膬?nèi)容是java中什么是堆排序？堆排序介紹。有一定的參考價(jià)值，有需要的朋友可以參考一下，希望對你們有所幫助。

• 堆排序介紹：
  堆排序可以分為兩個(gè)階段。在堆的構(gòu)造階段，我們將原始數(shù)組重新組織安排進(jìn)一個(gè)堆中；然后在下沉排序階段，我們從堆中按順序取出所有元素并得到排序結(jié)果。
  1.堆的構(gòu)造，一個(gè)有效的方法是從右到左使用sink()下沉函數(shù)構(gòu)造子堆。數(shù)組的每個(gè)位置都有一個(gè)子堆的根節(jié)點(diǎn)，sink()對于這些子堆也適用，如果一個(gè)節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都已經(jīng)是堆了，那么在該節(jié)點(diǎn)上調(diào)用sink()方法可以把他們合并成一個(gè)堆。我們可以跳過大小為1的子堆，因?yàn)榇笮?的不需要sink()也就是下沉操作，有關(guān)下沉和上浮操作可以參考我寫的優(yōu)先隊(duì)列那篇。
  2.堆的排序，我們通過第一步操作構(gòu)造了一個(gè)堆，在這個(gè)堆中，根節(jié)點(diǎn)永遠(yuǎn)是最大值的節(jié)點(diǎn)，所以我們把根節(jié)點(diǎn)的值與數(shù)組最后的值進(jìn)行交換，在使用sink()下沉來維護(hù)堆的結(jié)構(gòu)即可。

• 具體代碼實(shí)現(xiàn):

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;i++) {
			System.out.print(a[i]+" ");
		}	
	}
	//排序方法
	public static void sort(int[] a){
			int N = a.length-1;
			//通過下沉操作構(gòu)造堆,因?yàn)橄聵?biāo)從0開始，所以子節(jié)點(diǎn)為2*k+1和2*k+2;
			for(int k = (N-2)/2;k>=0;k--){
				sink(a,k,N);
			}
			//通過不斷把堆中最大值放到數(shù)組的后面來排序
			while(N>0){
				exch(a,0,N--);
				sink(a,0,N);
			}
	}
	//下沉函數(shù)
	private static void sink(int[] a, int i, int n){
		while(2*i+1<=n){
			int j = 2*i+1;
			if(j<n&&a[j]<a[j+1]) j++;
			if(a[i]>a[j]) break;
			exch(a,i,j);
			i=j;
		}
	}
	//交換函數(shù)
	private static void exch(int[] a, int i, int j){
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}
}

運(yùn)行結(jié)果:

以上就是java中什么是堆排序？堆排序介紹的詳細(xì)內(nèi)容，更多請關(guān)注億速云其它相關(guān)文章！