詳解堆排序算法原理及Java版的代碼實現(xiàn)
概述
堆排序是一種樹形選擇排序，是對直接選擇排序的有效改進(jìn)。
堆的定義如下：具有n個元素的序列(k1,k2,...,kn), 當(dāng)且僅當(dāng)滿足:
時稱之為堆。由堆的定義可以看出，堆頂元素（即第一個元素）必為最小項（小頂堆）或最大項（大頂堆）。
若以一維數(shù)組存儲一個堆，則堆對應(yīng)一棵完全二叉樹，且所有非葉結(jié)點（有子女的結(jié)點）的值均不大于(或不小于)其子女的值，根結(jié)點（堆頂元素）的值是最小(或最大)的。
(a)大頂堆序列：(96, 83, 27, 38, 11, 09)
(b)小頂堆序列：(12, 36, 24, 85, 47, 30, 53, 91)
初始時把要排序的n 個數(shù)的序列看作是一棵順序存儲的二叉樹（一維數(shù)組存儲二叉樹），調(diào)整它們的存儲序，使之成為一個堆，將堆頂元素輸出，得到n 個元素中最小(或最大)的元素。然后對剩下的n-1個元素重新調(diào)整使之成為堆，輸出堆頂元素，得到n 個元素中次小(或次大)的元素。依此類推，直到最后得到有n個節(jié)點的有序序列。稱這個過程為堆排序。
步驟&實例
實現(xiàn)堆排序需解決兩個問題：
(1)如何將n 個待排序的數(shù)建成堆；
(2)輸出堆頂元素后，怎樣調(diào)整剩余n-1 個元素，使其成為一個新堆。
建堆方法（小頂堆）：
對初始序列建堆的過程，就是一個反復(fù)進(jìn)行篩選的過程。
n 個結(jié)點的完全二叉樹，則最后一個結(jié)點是第n/2個結(jié)點的子樹。
篩選從第n/2個結(jié)點為根的子樹開始（n/2是最后一個有子樹的結(jié)點），使該子樹成為堆。
之后向前依次對各結(jié)點為根的子樹進(jìn)行篩選，使之成為堆，直到根結(jié)點。
如圖建堆初始過程
無序序列：(49, 38, 65, 97, 76, 13, 27, 49)
(a) 無序序列，初始二叉樹，97（第8/2=4個結(jié)點）為最后一個結(jié)點（49）的父結(jié)點。
(b) 97>=49,替換位置，接下來對n/2的上一個結(jié)點65進(jìn)行篩選。
(c) 13<=27且65>=13,替換65和13的位置，接下來對38進(jìn)行替換（都大于它，不需操作），對49進(jìn)行篩選。
(d) 13<=38且49>=13,替換49和13的位置，49>=27,替換49和27的位置。
(e) 最終得到一個堆，13是我們得到的最小數(shù)。
調(diào)整堆的方法（小頂堆）：
設(shè)有m 個元素的堆，輸出堆頂元素后，剩下m-1 個元素。將堆底元素送入堆頂，堆被破壞，其原因僅是根結(jié)點不滿足堆的性質(zhì)。
將根結(jié)點與左、右子樹中較小元素的進(jìn)行交換。
若與左子樹交換：如果左子樹堆被破壞，則重復(fù)方法(2).
若與右子樹交換，如果右子樹堆被破壞，則重復(fù)方法(2).
繼續(xù)對不滿足堆性質(zhì)的子樹進(jìn)行上述交換操作，直到葉子結(jié)點，堆被建成。
調(diào)整堆只需考慮被破壞的結(jié)點，其他的結(jié)點不需調(diào)整。
代碼實現(xiàn)(Java)
運行代碼結(jié)合注釋與上面的實例步驟進(jìn)行對比思考。
package com.coder4j.main;
public class HeapSort {
/**
* 調(diào)整為小頂堆（排序后結(jié)果為從大到小）
*
* @param array是待調(diào)整的堆數(shù)組
* @param s是待調(diào)整的數(shù)組元素的位置
* @param length是數(shù)組的長度
*
*/
public static void heapAdjustS(int[] array, int s, int length) {
int tmp = array[s];
int child = 2 * s + 1;// 左孩子結(jié)點的位置
System.out.println("待調(diào)整結(jié)點為：array[" + s + "] = " + tmp);
while (child < length) {
// child + 1 是當(dāng)前調(diào)整結(jié)點的右孩子
// 如果有右孩子且小于左孩子，使用右孩子與結(jié)點進(jìn)行比較，否則使用左孩子
if (child + 1 < length && array[child] > array[child + 1]) {
child++;
}
System.out.println("將與子孩子 array[" + child + "] = " + array[child] + " 進(jìn)行比較");
// 如果較小的子孩子比此結(jié)點小
if (array[s] > array[child]) {
System.out.println("子孩子比其小，交換位置");
array[s] = array[child];// 把較小的子孩子向上移動，替換當(dāng)前待調(diào)整結(jié)點
s = child;// 待調(diào)整結(jié)點移動到較小子孩子原來的位置
array[child] = tmp;
child = 2 * s + 1;// 繼續(xù)判斷待調(diào)整結(jié)點是否需要繼續(xù)調(diào)整
if (child >= length) {
System.out.println("沒有子孩子了，調(diào)整結(jié)束");
} else {
System.out.println("繼續(xù)與新的子孩子進(jìn)行比較");
}
// continue;
} else {
System.out.println("子孩子均比其大，調(diào)整結(jié)束");
break;// 當(dāng)前待調(diào)整結(jié)點小于它的左右孩子，不需調(diào)整，直接退出
}
}
}
/**
* 調(diào)整為大頂堆（排序后結(jié)果為從小到大）
*
* @param array是待調(diào)整的堆數(shù)組
* @param s是待調(diào)整的數(shù)組元素的位置
* @param length是數(shù)組的長度
*
*/
public static void heapAdjustB(int[] array, int s, int length) {
int tmp = array[s];
int child = 2 * s + 1;// 左孩子結(jié)點的位置
System.out.println("待調(diào)整結(jié)點為：array[" + s + "] = " + tmp);
while (child < length) {
// child + 1 是當(dāng)前調(diào)整結(jié)點的右孩子
// 如果有右孩子且大于左孩子，使用右孩子與結(jié)點進(jìn)行比較，否則使用左孩子
if (child + 1 < length && array[child] < array[child + 1]) {
child++;
}
System.out.println("將與子孩子 array[" + child + "] = " + array[child] + " 進(jìn)行比較");
// 如果較大的子孩子比此結(jié)點大
if (array[s] < array[child]) {
System.out.println("子孩子比其大，交換位置");
array[s] = array[child];// 把較大的子孩子向上移動，替換當(dāng)前待調(diào)整結(jié)點
s = child;// 待調(diào)整結(jié)點移動到較大子孩子原來的位置
array[child] = tmp;
child = 2 * s + 1;// 繼續(xù)判斷待調(diào)整結(jié)點是否需要繼續(xù)調(diào)整
if (child >= length) {
System.out.println("沒有子孩子了，調(diào)整結(jié)束");
} else {
System.out.println("繼續(xù)與新的子孩子進(jìn)行比較");
}
// continue;
} else {
System.out.println("子孩子均比其小，調(diào)整結(jié)束");
break;// 當(dāng)前待調(diào)整結(jié)點大于它的左右孩子，不需調(diào)整，直接退出
}
}
}
/**
* 堆排序算法
*
* @param array
* @param inverse true 為倒序排列，false 為正序排列
*/
public static void heapSort(int[] array, boolean inverse) {
// 初始堆
// 最后一個有孩子的結(jié)點位置 i = (length - 1) / 2, 以此向上調(diào)整各結(jié)點使其符合堆
System.out.println("初始堆開始");
for (int i = (array.length - 1) / 2; i >= 0; i--) {
if (inverse) {
heapAdjustS(array, i, array.length);
} else {
heapAdjustB(array, i, array.length);
}
}
System.out.println("初始堆結(jié)束");
for (int i = array.length - 1; i > 0; i--) {
// 交換堆頂元素H[0]和堆中最后一個元素
int tmp = array[i];
array[i] = array[0];
array[0] = tmp;
// 每次交換堆頂元素和堆中最后一個元素之后，都要對堆進(jìn)行調(diào)整
if (inverse) {
heapAdjustS(array, 0, i);
} else {
heapAdjustB(array, 0, i);
}
}
}
public static void main(String[] args) {
int[] array = { 49, 38, 65, 97, 76, 13, 27, 49 };
heapSort(array, false);
for (int i : array) {
System.out.print(i + " ");
}
}
}
運行結(jié)果：
初始堆開始 待調(diào)整結(jié)點為：array[3] = 97 將與子孩子 array[7] = 49 進(jìn)行比較 子孩子比其小，交換位置 沒有子孩子了，調(diào)整結(jié)束 待調(diào)整結(jié)點為：array[2] = 65 將與子孩子 array[5] = 13 進(jìn)行比較 子孩子比其小，交換位置 沒有子孩子了，調(diào)整結(jié)束 待調(diào)整結(jié)點為：array[1] = 38 將與子孩子 array[3] = 49 進(jìn)行比較 子孩子均比其大，調(diào)整結(jié)束 待調(diào)整結(jié)點為：array[0] = 49 將與子孩子 array[2] = 13 進(jìn)行比較 子孩子比其小，交換位置 繼續(xù)與新的子孩子進(jìn)行比較 將與子孩子 array[6] = 27 進(jìn)行比較 子孩子比其小，交換位置 沒有子孩子了，調(diào)整結(jié)束 初始堆結(jié)束 待調(diào)整結(jié)點為：array[0] = 97 將與子孩子 array[2] = 27 進(jìn)行比較 子孩子比其小，交換位置 繼續(xù)與新的子孩子進(jìn)行比較 將與子孩子 array[6] = 49 進(jìn)行比較 子孩子比其小，交換位置 沒有子孩子了，調(diào)整結(jié)束 待調(diào)整結(jié)點為：array[0] = 97 將與子孩子 array[1] = 38 進(jìn)行比較 子孩子比其小，交換位置 繼續(xù)與新的子孩子進(jìn)行比較 將與子孩子 array[3] = 49 進(jìn)行比較 子孩子比其小，交換位置 沒有子孩子了，調(diào)整結(jié)束 待調(diào)整結(jié)點為：array[0] = 65 將與子孩子 array[1] = 49 進(jìn)行比較 子孩子比其小，交換位置 繼續(xù)與新的子孩子進(jìn)行比較 將與子孩子 array[4] = 76 進(jìn)行比較 子孩子均比其大，調(diào)整結(jié)束 待調(diào)整結(jié)點為：array[0] = 76 將與子孩子 array[2] = 49 進(jìn)行比較 子孩子比其小，交換位置 沒有子孩子了，調(diào)整結(jié)束 待調(diào)整結(jié)點為：array[0] = 97 將與子孩子 array[1] = 65 進(jìn)行比較 子孩子比其小，交換位置 沒有子孩子了，調(diào)整結(jié)束 待調(diào)整結(jié)點為：array[0] = 76 將與子孩子 array[1] = 97 進(jìn)行比較 子孩子均比其大，調(diào)整結(jié)束 待調(diào)整結(jié)點為：array[0] = 97 97 76 65 49 49 38 27 13
PS：堆排序與直接插入排序的區(qū)別
直接選擇排序中，為了從R[1..n]中選出關(guān)鍵字最小的記錄，必須進(jìn)行n-1次比較，然后在R[2..n]中選出關(guān)鍵字最小的記錄，又需要做n-2次比較。事實上，后面的n-2次比較中，有許多比較可能在前面的n-1次比較中已經(jīng)做過，但由于前一趟排序時未保留這些比較結(jié)果，所以后一趟排序時又重復(fù)執(zhí)行了這些比較操作。
堆排序可通過樹形結(jié)構(gòu)保存部分比較結(jié)果，可減少比較次數(shù)。
相關(guān)文章
這篇文章主要介紹了Spring中的依賴注入DI詳解,組件之間依賴關(guān)系由容器在運行期決定,形象的說,即由容器動態(tài)的將依賴關(guān)系注入到組件之中,依賴注入的目的并非為軟件系統(tǒng)帶來更多功能,是為了提升組件重用的頻率,并為系統(tǒng)搭建一個靈活、可擴(kuò)展的平臺,需要的朋友可以參考下2024-01-01
如何使用SpringMVC的消息轉(zhuǎn)換器設(shè)置日期格式
這篇文章主要介紹了如何使用SpringMVC的消息轉(zhuǎn)換器設(shè)置日期格式問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-07-07
這篇文章主要介紹了使用SpringBoot配置https(SSL證書)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-12-12
Java使用JSONPath解析JSON完整內(nèi)容詳解
這篇文章主要介紹了Java使用JSONPath解析JSON完整內(nèi)容詳解，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03
淺析Bean?Searcher?與?MyBatis?Plus?區(qū)別介紹
Bean?Searcher號稱任何復(fù)雜的查詢都可以一行代碼搞定，但?Mybatis?Plus?似乎也有類似的動態(tài)查詢功能，最近火起的?Bean?Searcher?與?MyBatis?Plus?倒底有啥區(qū)別？帶著這個問題一起通過本文學(xué)習(xí)下吧2022-05-05
JDBC用IDEA連接SQLServer數(shù)據(jù)庫的超實用教程
JDBC是Java連接數(shù)據(jù)庫的一種接口,它由各個數(shù)據(jù)庫廠商為開發(fā)者提供的接口,要使用它需要到相應(yīng)廠商下載對應(yīng)的jar包,下面這篇文章主要給大家介紹了關(guān)于JDBC用IDEA連接SQLServer數(shù)據(jù)庫的超實用教程,需要的朋友可以參考下2023-05-05
這篇文章主要介紹了Spring集成Redis詳解代碼示例，介紹了Eclipse工程結(jié)構(gòu)，POM依賴，Spring配置，Redis配置信息以及Java代碼等相關(guān)內(nèi)容，具有一定參考價值，需要的朋友可以了解下。2017-11-11
ldc指令將int、float、或者一個類、方法類型或方法句柄的符號引用、還可能是String型常量值從常量池中推送至棧頂。這一篇介紹一個虛擬機(jī)規(guī)范中定義的一個字節(jié)碼指令ldc，另外還有一個虛擬機(jī)內(nèi)部使用的字節(jié)碼指令_fast_aldc。需要的盆友可參考下面文章的內(nèi)容2021-09-09
spring-boot @Component和@Bean的區(qū)別詳解
這篇文章主要介紹了spring-boot @Component和@Bean的區(qū)別詳解,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-07-07
這篇文章主要介紹了詳解Maven私服Nexus的安裝與使用，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2018-03-03