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è)堆。我們可以跳過(guò)大小為1的子堆，因?yàn)榇笮?的不需要sink()也就是下沉操作，有關(guān)下沉和上浮操作可以參考我寫(xiě)的優(yōu)先隊(duì)列那篇。
2.堆的排序，我們通過(guò)第一步操作構(gòu)造了一個(gè)堆，在這個(gè)堆中，根節(jié)點(diǎn)永遠(yuǎn)是最大值的節(jié)點(diǎn)，所以我們把根節(jié)點(diǎn)的值與數(shù)組最后的值進(jìn)行交換，在使用sink()下沉來(lái)維護(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;
//通過(guò)下沉操作構(gòu)造堆,因?yàn)橄聵?biāo)從0開(kāi)始，所以子節(jié)點(diǎn)為2*k+1和2*k+2;
for(int k = (N-2)/2;k>=0;k--){
sink(a,k,N);
}
//通過(guò)不斷把堆中最大值放到數(shù)組的后面來(lái)排序
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)文章
富文本編輯器是一種能夠編輯和展示富文本內(nèi)容的工具或程序,與純文本編輯器不同,富文本編輯器可以處理文本的格式、樣式、布局等方面,使文本更加豐富多樣,本文給大家介紹了SpringBoot添加富文本編輯器操作步驟,需要的朋友可以參考下2024-01-01
Spring MVC項(xiàng)目中l(wèi)og4J和AOP使用詳解
項(xiàng)目日志記錄是項(xiàng)目開(kāi)發(fā)、運(yùn)營(yíng)必不可少的內(nèi)容，有了它可以對(duì)系統(tǒng)有整體的把控，出現(xiàn)任何問(wèn)題都有蹤跡可尋。下面這篇文章主要給大家介紹了關(guān)于Spring MVC項(xiàng)目中l(wèi)og4J和AOP使用的相關(guān)資料，需要的朋友可以參考下。2017-12-12
這篇文章主要介紹了淺談Java8新特性Predicate接口,文中有非常詳細(xì)的代碼示例,對(duì)正在學(xué)習(xí)java的小伙伴們有很好的幫助,需要的朋友可以參考下2021-05-05
用C++實(shí)現(xiàn)求N!中末尾0的個(gè)數(shù)的方法詳解
這篇文章主要介紹了用C++實(shí)現(xiàn)求N!中末尾0的個(gè)數(shù)的方法詳解，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-07-07
springboot熱部署class XX cannot be cast&nbs
在使用DevTools進(jìn)行熱加載時(shí)遇到的`classXXcannotbecasttoclassXX`錯(cuò)誤,以及解決該問(wèn)題的方法,通過(guò)在`resources`目錄下創(chuàng)建`META-INF/spring-devtools.properties`文件,并添加相應(yīng)的配置,可以有效解決此問(wèn)題,使DevTools熱加載功能得以正常工作2025-02-02
這篇文章主要介紹了Java常用字節(jié)流和字符流實(shí)例匯總,文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-07-07
這篇文章主要介紹了Spring整合redis的操作代碼，本文通過(guò)實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定參考借鑒價(jià)值,需要的朋友可以參考下2022-02-02
基于maven搭建一個(gè)ssm的web項(xiàng)目的詳細(xì)圖文教程
這篇文章主要介紹了基于maven搭建一個(gè)ssm的web項(xiàng)目的詳細(xì)教程,本文通過(guò)圖文并茂的形式給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2020-09-09
java寫(xiě)入zip文件后無(wú)法進(jìn)行刪除的問(wèn)題及解決
這篇文章主要介紹了java寫(xiě)入zip文件后無(wú)法進(jìn)行刪除的問(wèn)題及解決方案,具有很好的參考價(jià)值,希望對(duì)大家有所幫助,如有錯(cuò)誤或未考慮完全的地方,望不吝賜教2024-06-06
這篇文章主要介紹了Java多線程中斷機(jī)制三種方法及示例，向大家分享了這三種方法的介紹幾代碼示例，具有一定參考價(jià)值，需要的朋友可以了解下。2017-11-11