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