詳解堆排序算法原理及Java版的代碼實現(xià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ù)進行篩選的過程。
n 個結(jié)點的完全二叉樹，則最后一個結(jié)點是第n/2個結(jié)點的子樹。
篩選從第n/2個結(jié)點為根的子樹開始（n/2是最后一個有子樹的結(jié)點），使該子樹成為堆。
之后向前依次對各結(jié)點為根的子樹進行篩選，使之成為堆，直到根結(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進行篩選。
(c) 13<=27且65>=13,替換65和13的位置，接下來對38進行替換（都大于它，不需操作），對49進行篩選。
(d) 13<=38且49>=13,替換49和13的位置，49>=27,替換49和27的位置。
(e) 最終得到一個堆，13是我們得到的最小數(shù)。
調(diào)整堆的方法（小頂堆）：
設(shè)有m 個元素的堆，輸出堆頂元素后，剩下m-1 個元素。將堆底元素送入堆頂，堆被破壞，其原因僅是根結(jié)點不滿足堆的性質(zhì)。
將根結(jié)點與左、右子樹中較小元素的進行交換。
若與左子樹交換：如果左子樹堆被破壞，則重復(fù)方法(2).
若與右子樹交換，如果右子樹堆被破壞，則重復(fù)方法(2).
繼續(xù)對不滿足堆性質(zhì)的子樹進行上述交換操作，直到葉子結(jié)點，堆被建成。
調(diào)整堆只需考慮被破壞的結(jié)點，其他的結(jié)點不需調(diào)整。
代碼實現(xiàn)(Java)
運行代碼結(jié)合注釋與上面的實例步驟進行對比思考。
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é)點進行比較，否則使用左孩子
if (child + 1 < length && array[child] > array[child + 1]) {
child++;
}
System.out.println("將與子孩子 array[" + child + "] = " + array[child] + " 進行比較");
// 如果較小的子孩子比此結(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ù)與新的子孩子進行比較");
}
// 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é)點進行比較，否則使用左孩子
if (child + 1 < length && array[child] < array[child + 1]) {
child++;
}
System.out.println("將與子孩子 array[" + child + "] = " + array[child] + " 進行比較");
// 如果較大的子孩子比此結(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ù)與新的子孩子進行比較");
}
// 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;
// 每次交換堆頂元素和堆中最后一個元素之后，都要對堆進行調(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 進行比較 子孩子比其小，交換位置 沒有子孩子了，調(diào)整結(jié)束 待調(diào)整結(jié)點為：array[2] = 65 將與子孩子 array[5] = 13 進行比較 子孩子比其小，交換位置 沒有子孩子了，調(diào)整結(jié)束 待調(diào)整結(jié)點為：array[1] = 38 將與子孩子 array[3] = 49 進行比較 子孩子均比其大，調(diào)整結(jié)束 待調(diào)整結(jié)點為：array[0] = 49 將與子孩子 array[2] = 13 進行比較 子孩子比其小，交換位置 繼續(xù)與新的子孩子進行比較 將與子孩子 array[6] = 27 進行比較 子孩子比其小，交換位置 沒有子孩子了，調(diào)整結(jié)束 初始堆結(jié)束 待調(diào)整結(jié)點為：array[0] = 97 將與子孩子 array[2] = 27 進行比較 子孩子比其小，交換位置 繼續(xù)與新的子孩子進行比較 將與子孩子 array[6] = 49 進行比較 子孩子比其小，交換位置 沒有子孩子了，調(diào)整結(jié)束 待調(diào)整結(jié)點為：array[0] = 97 將與子孩子 array[1] = 38 進行比較 子孩子比其小，交換位置 繼續(xù)與新的子孩子進行比較 將與子孩子 array[3] = 49 進行比較 子孩子比其小，交換位置 沒有子孩子了，調(diào)整結(jié)束 待調(diào)整結(jié)點為：array[0] = 65 將與子孩子 array[1] = 49 進行比較 子孩子比其小，交換位置 繼續(xù)與新的子孩子進行比較 將與子孩子 array[4] = 76 進行比較 子孩子均比其大，調(diào)整結(jié)束 待調(diào)整結(jié)點為：array[0] = 76 將與子孩子 array[2] = 49 進行比較 子孩子比其小，交換位置 沒有子孩子了，調(diào)整結(jié)束 待調(diào)整結(jié)點為：array[0] = 97 將與子孩子 array[1] = 65 進行比較 子孩子比其小，交換位置 沒有子孩子了，調(diào)整結(jié)束 待調(diào)整結(jié)點為：array[0] = 76 將與子孩子 array[1] = 97 進行比較 子孩子均比其大，調(diào)整結(jié)束 待調(diào)整結(jié)點為：array[0] = 97 97 76 65 49 49 38 27 13
PS：堆排序與直接插入排序的區(qū)別
直接選擇排序中，為了從R[1..n]中選出關(guā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)文章
這篇文章主要介紹了Mybatis 實現(xiàn)打印sql語句的代碼,本文通過實例代碼給大家介紹的非常詳細，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-07-07
springboot結(jié)合mybatis-plus快速生成項目模板的方法
Mybatis-Plus是一個 Mybatis 的增強工具，在 Mybatis 的基礎(chǔ)上只做增強不做改變，為簡化開發(fā)、提高效率而生，接下來通過本文給大家分享springboot結(jié)合mybatis-plus快速生成項目模板的方法，感興趣的朋友一起看看吧2021-06-06
SpringBoot使用Sa-Token實現(xiàn)登錄認(rèn)證
本文主要介紹了SpringBoot使用Sa-Token實現(xiàn)登錄認(rèn)證，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2023-04-04
Spring?Boot?Admin?添加報警提醒和登錄驗證功能的具體實現(xiàn)
報警提醒功能是基于郵箱實現(xiàn)的，當(dāng)然也可以使用其他的提醒功能，如釘釘或飛書機器人提醒也是可以的，但郵箱報警功能的實現(xiàn)成本最低，所以本文我們就來看郵箱的報警提醒功能的具體實現(xiàn)2022-01-01
使用java.nio.file?庫優(yōu)雅的操作文件詳解
這篇文章主要介紹了使用java.nio.file?庫優(yōu)雅的操作文件詳解,需要的朋友可以參考下2023-05-05
這篇文章主要為大家詳細介紹了spring boot實現(xiàn)文件上傳，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2022-08-08
SpringBoot在IDEA中實現(xiàn)熱部署的步驟
這篇文章主要介紹了SpringBoot在IDEA中實現(xiàn)熱部署的步驟，幫助大家更好的理解和使用springboot框架，感興趣的朋友可以了解下2020-11-11
這篇文章主要為大家詳細介紹了java處理圖片背景顏色的方法，藍底寸照批量轉(zhuǎn)換為白底，具有一定的參考價值，感興趣的小伙伴們可以參考一下2018-04-04
基于selenium-java封裝chrome、firefox、phantomjs實現(xiàn)爬蟲
這篇文章主要介紹了基于selenium-java封裝chrome、firefox、phantomjs實現(xiàn)爬蟲，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2020-10-10
spring-boot-starter-validation?校驗參數(shù)的實現(xiàn)
參數(shù)校驗在很多地方都可以用到，本文主要介紹了spring-boot-starter-validation?校驗參數(shù)的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2022-04-04