java堆排序概念原理介紹
更新時間：2018年10月23日 08:38:08 投稿：laozhang
在本篇文章里我們給大家分享了關(guān)于java堆排序的概念原理相關(guān)知識點內(nèi)容，有需要的朋友們可以學(xué)習(xí)下。
堆排序介紹：
堆排序可以分為兩個階段。在堆的構(gòu)造階段，我們將原始數(shù)組重新組織安排進(jìn)一個堆中；然后在下沉排序階段，我們從堆中按順序取出所有元素并得到排序結(jié)果。
1.堆的構(gòu)造，一個有效的方法是從右到左使用sink()下沉函數(shù)構(gòu)造子堆。數(shù)組的每個位置都有一個子堆的根節(jié)點，sink()對于這些子堆也適用，如果一個節(jié)點的兩個子節(jié)點都已經(jīng)是堆了，那么在該節(jié)點上調(diào)用sink()方法可以把他們合并成一個堆。我們可以跳過大小為1的子堆，因為大小為1的不需要sink()也就是下沉操作，有關(guān)下沉和上浮操作可以參考我寫的優(yōu)先隊列那篇。
2.堆的排序，我們通過第一步操作構(gòu)造了一個堆，在這個堆中，根節(jié)點永遠(yuǎn)是最大值的節(jié)點，所以我們把根節(jié)點的值與數(shù)組最后的值進(jìn)行交換，在使用sink()下沉來維護(hù)堆的結(jié)構(gòu)即可。
具體代碼實現(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)造堆,因為下標(biāo)從0開始，所以子節(jié)點為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;
}
}
運行結(jié)果:
相關(guān)文章
SpringCloud Finchley+Spring Boot 2.0 集成Consul的方法示例(1.2版本)
這篇文章主要介紹了SpringCloud Finchley+Spring Boot 2.0 集成Consul的方法示例(1.2版本)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-08-08
java.util.Properties集合繼承于Hashtable,來表示一個持久的屬性集,他使用鍵值結(jié)構(gòu)存儲數(shù)據(jù),每個鍵及其對應(yīng)的值都是一個字符串,該類被許多java類使用,下面這篇文章主要給大家介紹了關(guān)于如何快速上手Java中Properties集合類的相關(guān)資料,需要的朋友可以參考下2023-02-02
詳解Spring?Security?捕獲?filter?層面異常返回我們自定義的內(nèi)容
Spring?的異常會轉(zhuǎn)發(fā)到?BasicErrorController?中進(jìn)行異常寫入，然后才會返回客戶端。所以，我們可以在?BasicErrorController?對?filter異常進(jìn)行捕獲并處理，下面通過本文給大家介紹Spring?Security?捕獲?filter?層面異常，返回我們自定義的內(nèi)容，感興趣的朋友一起看看吧2022-05-05
這篇文章主要給大家介紹了關(guān)于Java系統(tǒng)中拆分同步和異步的相關(guān)資料，文中通過示例代碼介紹的非常詳細(xì)，對大家學(xué)習(xí)或者使用Java具有一定的參考學(xué)習(xí)價值，需要的朋友們下面來一起學(xué)習(xí)學(xué)習(xí)吧2019-06-06
Spring?Security?是一個基于?Spring?框架的安全框架,提供了一套安全性認(rèn)證和授權(quán)的解決方案,用于保護(hù)?Web?應(yīng)用程序和服務(wù),接下來小編就和大家聊聊Spring?Security,感興趣的小伙伴跟著小編一起來看看吧2023-08-08
這篇文章主要為大家詳細(xì)介紹了java實現(xiàn)二叉樹遍歷的四種方式，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能給你帶來幫助2021-08-08
這篇文章主要介紹了Java笛卡爾積算法原理與實現(xiàn)方法,結(jié)合實例形式較為詳細(xì)的分析了笛卡爾積算法的原理及java定義與使用笛卡爾積算法的相關(guān)操作技巧,需要的朋友可以參考下2017-12-12
Spring?Boot中KafkaListener的介紹、原理和使用方法案例詳解
本文介紹了Spring Boot中 @KafkaListener 注解的介紹、原理和使用方法，通過本文的介紹，我們希望讀者能夠更好地理解Spring Boot中 @KafkaListener 注解的使用方法，并在項目中更加靈活地應(yīng)用2023-09-09
Sentinel實現(xiàn)動態(tài)配置的集群流控的方法
這篇文章主要介紹了Sentinel實現(xiàn)動態(tài)配置的集群流控,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2021-04-04
SpringBoot3 Spring WebFlux簡介(推薦)
SpringWebFlux是Spring Framework 5中引入的響應(yīng)式Web框架,用于支持非阻塞異步通信和響應(yīng)式流處理,與傳統(tǒng)的SpringMVC相比,WebFlux提供了完全異步非阻塞的編程模型,適用高并發(fā)、微服務(wù)架構(gòu)和實時數(shù)據(jù)流,本文介紹SpringBoot3 Spring WebFlux簡介,感興趣的朋友一起看看吧2024-10-10