堆排序（Heapsort）是指利用堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計(jì)的一種排序算法。堆積是一個(gè)近似完全二叉樹(shù)的結(jié)構(gòu)，并同時(shí)滿(mǎn)足堆積的性質(zhì)：即子結(jié)點(diǎn)的鍵值或索引總是小于（或者大于）它的父節(jié)點(diǎn)。

創(chuàng)新互聯(lián)建站專(zhuān)注為客戶(hù)提供全方位的互聯(lián)網(wǎng)綜合服務(wù)，包含不限于成都做網(wǎng)站、網(wǎng)站建設(shè)、外貿(mào)營(yíng)銷(xiāo)網(wǎng)站建設(shè)、桐鄉(xiāng)網(wǎng)絡(luò)推廣、微信小程序定制開(kāi)發(fā)、桐鄉(xiāng)網(wǎng)絡(luò)營(yíng)銷(xiāo)、桐鄉(xiāng)企業(yè)策劃、桐鄉(xiāng)品牌公關(guān)、搜索引擎seo、人物專(zhuān)訪(fǎng)、企業(yè)宣傳片、企業(yè)代運(yùn)營(yíng)等，從售前售中售后，我們都將竭誠(chéng)為您服務(wù)，您的肯定，是我們最大的嘉獎(jiǎng)；創(chuàng)新互聯(lián)建站為所有大學(xué)生創(chuàng)業(yè)者提供桐鄉(xiāng)建站搭建服務(wù)，24小時(shí)服務(wù)熱線(xiàn)：13518219792，官方網(wǎng)址：www.rwnh.cn

堆排序的平均時(shí)間復(fù)雜度為Ο(nlogn) 。

算法步驟：

1. 創(chuàng)建一個(gè)堆H[0..n-1]

2. 把堆首（最大值）和堆尾互換

3. 把堆的尺寸縮小1，并調(diào)用shift_down(0),目的是把新的數(shù)組頂端數(shù)據(jù)調(diào)整到相應(yīng)位置

4. 重復(fù)步驟2，直到堆的尺寸為1

堆：

堆實(shí)際上是一棵完全二叉樹(shù)，其任何一非葉節(jié)點(diǎn)滿(mǎn)足性質(zhì)： Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]或者Key[i]>=Key[2i+1]&&key>=key[2i+2] 即任何一非葉節(jié)點(diǎn)的關(guān)鍵字不大于或者不小于其左右孩子節(jié)點(diǎn)的關(guān)鍵字。 堆分為大頂堆和小頂堆，滿(mǎn)足Key[i]>=Key[2i+1]&&key>=key[2i+2]稱(chēng)為大頂堆，滿(mǎn)足 Key[i]<=key[2i+1]&&Key[i]<=key[2i+2]稱(chēng)為小頂堆。由上述性質(zhì)可知大頂堆的堆頂?shù)年P(guān)鍵字肯定是所有關(guān)鍵字中最大的，小頂堆的堆頂?shù)年P(guān)鍵字是所有關(guān)鍵字中最小的。

堆排序思想：

利用大頂堆(小頂堆)堆頂記錄的是最大關(guān)鍵字(最小關(guān)鍵字)這一特性，使得每次從無(wú)序中選擇最大記錄(最小記錄)變得簡(jiǎn)單。 其基本思想為(大頂堆)： 1)將初始待排序關(guān)鍵字序列(R1,R2….Rn)構(gòu)建成大頂堆，此堆為初始的無(wú)序區(qū)； 2)將堆頂元素R[1]與最后一個(gè)元素R[n]交換，此時(shí)得到新的無(wú)序區(qū)(R1,R2,……Rn-1)和新的有序區(qū)(Rn),且滿(mǎn)足R[1,2...n-1]<=R[n]; 3)由于交換后新的堆頂R[1]可能違反堆的性質(zhì)，因此需要對(duì)當(dāng)前無(wú)序區(qū)(R1,R2,……Rn-1)調(diào)整為新堆，然后再次將R[1]與無(wú)序區(qū)最后一個(gè)元素交換，得到新的無(wú)序區(qū)(R1,R2….Rn-2)和新的有序區(qū)(Rn-1,Rn)。不斷重復(fù)此過(guò)程直到有序區(qū)的元素個(gè)數(shù)為n-1，則整個(gè)排序過(guò)程完成。 操作過(guò)程如下： 1)初始化堆：將R[1..n]構(gòu)造為堆； 2)將當(dāng)前無(wú)序區(qū)的堆頂元素R[1]同該區(qū)間的最后一個(gè)記錄交換，然后將新的無(wú)序區(qū)調(diào)整為新的堆。 因此對(duì)于堆排序，最重要的兩個(gè)操作就是構(gòu)造初始堆和調(diào)整堆，其實(shí)構(gòu)造初始堆事實(shí)上也是調(diào)整堆的過(guò)程，只不過(guò)構(gòu)造初始堆是對(duì)所有的非葉節(jié)點(diǎn)都進(jìn)行調(diào)整。

一個(gè)圖示實(shí)例

給定一個(gè)整形數(shù)組a[]={16,7,3,20,17,8}，對(duì)其進(jìn)行堆排序。 首先根據(jù)該數(shù)組元素構(gòu)建一個(gè)完全二叉樹(shù)，得到

然后需要構(gòu)造初始堆，則從最后一個(gè)非葉節(jié)點(diǎn)開(kāi)始調(diào)整，調(diào)整過(guò)程如下：

20和16交換后導(dǎo)致16不滿(mǎn)足堆的性質(zhì)，因此需重新調(diào)整

這樣就得到了初始堆。

先進(jìn)行一次調(diào)整時(shí)其成為大頂堆，

即每次調(diào)整都是從父節(jié)點(diǎn)、左孩子節(jié)點(diǎn)、右孩子節(jié)點(diǎn)三者中選擇最大者跟父節(jié)點(diǎn)進(jìn)行交換(交換之后可能造成被交換的孩子節(jié)點(diǎn)不滿(mǎn)足堆的性質(zhì)，因此每次交換之后要重新對(duì)被交換的孩子節(jié)點(diǎn)進(jìn)行調(diào)整)。有了初始堆之后就可以進(jìn)行排序了。

此時(shí)3位于堆頂不滿(mǎn)堆的性質(zhì)，則需調(diào)整繼續(xù)調(diào)整

這樣整個(gè)區(qū)間便已經(jīng)有序了。從上述過(guò)程可知，堆排序其實(shí)也是一種選擇排序，是一種樹(shù)形選擇排序。只不過(guò)直接選擇排序中，為了從R[1...n]中選擇最大記錄，需比較n-1次，然后從R[1...n-2]中選擇最大記錄需比較n-2次。事實(shí)上這n-2次比較中有很多已經(jīng)在前面的n-1次比較中已經(jīng)做過(guò)，而樹(shù)形選擇排序恰好利用樹(shù)形的特點(diǎn)保存了部分前面的比較結(jié)果，因此可以減少比較次數(shù)。對(duì)于n個(gè)關(guān)鍵字序列，最壞情況下每個(gè)節(jié)點(diǎn)需比較log2(n)次，因此其最壞情況下時(shí)間復(fù)雜度為nlogn。堆排序?yàn)椴环€(wěn)定排序，不適合記錄較少的排序。 上面描述了這么多，簡(jiǎn)而言之,堆排序的基本做法是:首先，用原始數(shù)據(jù)構(gòu)建成一個(gè)大(小)堆作為原始無(wú)序區(qū)，然后，每次取出堆頂元素，放入有序區(qū)。由于堆頂元素被取出來(lái)了，我們用堆中最后一個(gè)元素放入堆頂，如此，堆的性質(zhì)就被破壞了。我們需要重新對(duì)堆進(jìn)行調(diào)整，如此繼續(xù)N次，那么無(wú)序區(qū)的N個(gè)元素都被放入有序區(qū)了，也就完成了排序過(guò)程。
（建堆是自底向上）

實(shí)際應(yīng)用：

實(shí)際中我們進(jìn)行堆排序是為了取得一定條件下的最大值或最小值，例如：需要在100個(gè)數(shù)中找到10個(gè)最大值，因此我們定義一個(gè)大小為10的堆，把100中的前十個(gè)數(shù)據(jù)建立成小頂堆（堆頂最?。缓髲?00個(gè)數(shù)據(jù)中的第11個(gè)數(shù)據(jù)開(kāi)始與堆頂比較，若堆頂小于當(dāng)前數(shù)據(jù)，則把堆頂彈出，把當(dāng)前數(shù)據(jù)壓入堆頂，然后把數(shù)據(jù)從堆頂下移到一定位置即可，

代碼：

public class Test0 {
	static int[] arr;//堆數(shù)組，有效數(shù)組
	 public Test0(int m){
		arr= new int[m];
	}
	
	 static int m=0;
	static int size=0;//用來(lái)標(biāo)記堆中有效的數(shù)據(jù)
	public void addToSmall(int v){
		//int[] a = {16,4,5,9,1,10,11,12,13,14,15,2,3,6,7,8,111,222,333,555,66,67,54};
		//堆的大小為10
		//arr = new int[10];
		if(size<arr.length){
			arr[size]=v;
			add_sort(size);
			//add_sort1(size);
			size++;
		}else{
			arr[0]=v;
			add_sort1(0);								
		}

		
	}
	public void printSmall(){
		for(int i=0;i<size;i++){
			System.out.println(arr[i]);
		}
	}
	public void del(){ 
		size--;
		arr[0]=arr[9];
		add_sort1(0);
	}
	public void Small(int index){
		if(m<arr.length){
			add_sort(index);
			m++;
		}else{
			add_sort1(index);
			m++;
		}
	}
	public void add_sort( int index){//小頂堆，建堆
		/*
	  * 父節(jié)點(diǎn)坐標(biāo)：index
	  * 左孩子節(jié)點(diǎn)：index*2
	  * 右孩子節(jié)點(diǎn)：index*2+1
	  *若數(shù)組中最后一個(gè)為奇數(shù)則為 左孩子
	  *若數(shù)組中最后一個(gè)為偶數(shù)則為 右孩子
	      若孩子節(jié)點(diǎn)比父節(jié)點(diǎn)的值大，則進(jìn)行值交換，若右孩子比左孩子大則進(jìn)行值交換
		 * 
		 */
			int par;
			if(index!=0){
				if(index%2==0){
					par=(index-1)/2;
					if(arr[index]<arr[par]){
						swap(arr,index,par);
						add_sort(par);
					}
					if(arr[index]>arr[par*2]){
						swap(arr,index,par*2);
					if(arr[index]<arr[par]){
						swap(arr,index,par);
					}
					add_sort(par);
					}
					
				}else{
					par=index/2;
					if(arr[index]<arr[par]){
						swap(arr,index,par);
						add_sort(par);
					}
					if(arr[index]<arr[par*2+1]){
						swap(arr, index, par*2+1);
					if(arr[index]<arr[par]){
						swap(arr,index,par);
					}
					add_sort(par);
					}
				}
	
			}
		
		
	}
	public void add_sort1(int index){//調(diào)整小頂堆
		/*調(diào)整自頂向下
		 * 只要孩子節(jié)點(diǎn)比父節(jié)點(diǎn)的值大，就進(jìn)行值交換，
		 */
		int left=index*2;
		int right=index*2+1;
		int max=0;
		if(left<10&&arr[left]<arr[index]){
			max=left;
		}else{
			max=index;
		}
		if(right<10&&arr[right]<arr[max]){
			max=right;
		}
		if(max!=index){
			swap(arr,max,index);
			add_sort1(max);
		}
	}

}

測(cè)試代碼：
package 大頂堆;

import java.util.Scanner;

public class Main_test0 {
	public static void main(String args[]){
		Scanner scan = new Scanner(System.in);
		System.out.println("(小頂堆)請(qǐng)輸入堆大小：");
		int m=scan.nextInt();
		Test0 test = new Test0(m);
		int[] a = {16,4,5,9,1,10,11,12,13,14,15,2,3,6,7,8};
		for(int i=0;i<a.length;i++){
			test.addToSmall(a[i]);
		}
		test.printSmall();				
		test.del();
		test.printSmall();	
	
		scan.close();
	}
}

以上這篇Java 堆排序?qū)嵗?大頂堆、小頂堆)就是小編分享給大家的全部?jī)?nèi)容了，希望能給大家一個(gè)參考，也希望大家多多支持創(chuàng)新互聯(lián)。

當(dāng)前題目：Java堆排序?qū)嵗?大頂堆、小頂堆)
當(dāng)前鏈接：http://www.rwnh.cn/article22/igpcjc.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供微信小程序、網(wǎng)站導(dǎo)航、小程序開(kāi)發(fā)、定制網(wǎng)站、品牌網(wǎng)站建設(shè)、用戶(hù)體驗(yàn)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶(hù)投稿、用戶(hù)轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀(guān)點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話(huà)：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)