詳解堆排序算法道理及Java版的代碼完成。本站提示廣大學習愛好者：（詳解堆排序算法道理及Java版的代碼完成）文章只能為提供參考，不一定能成為您想要的結果。以下是詳解堆排序算法道理及Java版的代碼完成正文
概述
堆排序是一種樹形選擇排序，是對直接選擇排序的有用改良。
堆的界說以下：具有n個元素的序列(k1,k2,...,kn), 當且僅當知足:
時稱之為堆。由堆的界說可以看出，堆頂元素（即第一個元素）必為最小項（小頂堆）或最年夜項（年夜頂堆）。
若以一維數組存儲一個堆，則堆對應一棵完整二叉樹，且一切非葉結點（有後代的結點）的值均不年夜於(或不小於)其後代的值，根結點（堆頂元素）的值是最小(或最年夜)的。
(a)年夜頂堆序列：(96, 83, 27, 38, 11, 09)
(b)小頂堆序列：(12, 36, 24, 85, 47, 30, 53, 91)
初始時把要排序的n 個數的序列看做是一棵次序存儲的二叉樹（一維數組存儲二叉樹），調劑它們的存儲序，使之成為一個堆，將堆頂元素輸入，獲得n 個元素中最小(或最年夜)的元素。然後對剩下的n-1個元素從新調劑使之成為堆，輸入堆頂元素，獲得n 個元素中次小(或次年夜)的元素。依此類推，直到最初獲得有n個節點的有序序列。稱這個進程為堆排序。
步調&實例
完成堆排序需處理兩個成績：
(1)若何將n 個待排序的數建成堆；
(2)輸入堆頂元素後，如何調劑殘剩n-1 個元素，使其成為一個新堆。
建堆辦法（小頂堆）：
對初始序列建堆的進程，就是一個重復停止挑選的進程。
n 個結點的完整二叉樹，則最初一個結點是第n/2個結點的子樹。
挑選從第n/2個結點為根的子樹開端（n/2是最初一個有子樹的結點），使該子樹成為堆。
以後向前順次對各結點為根的子樹停止挑選，使之成為堆，直到根結點。
如圖建堆初始進程
無序序列：(49, 38, 65, 97, 76, 13, 27, 49)
(a) 無序序列，初始二叉樹，97（第8/2=4個結點）為最初一個結點（49）的父結點。
(b) 97>=49,調換地位，接上去對n/2的上一個結點65停止挑選。
(c) 13<=27且65>=13,調換65和13的地位，接上去對38停止調換（都年夜於它，不需操作），對49停止挑選。
(d) 13<=38且49>=13,調換49和13的地位，49>=27,調換49和27的地位。
(e) 終究獲得一個堆，13是我們獲得的最小數。
調劑堆的辦法（小頂堆）：
設有m 個元素的堆，輸入堆頂元素後，剩下m-1 個元素。將堆底元素送入堆頂，堆被損壞，其緣由僅是根結點不知足堆的性質。
將根結點與左、右子樹中較小元素的停止交流。
若與左子樹交流：假如左子樹堆被損壞，則反復辦法(2).
若與右子樹交流，假如右子樹堆被損壞，則反復辦法(2).
持續對不知足堆性質的子樹停止上述交流操作，直到葉子結點，堆被建成。
調劑堆只需斟酌被損壞的結點，其他的結點不需調劑。
代碼完成(Java)
運轉代碼聯合正文與下面的實例步調停止比較思慮。
package com.coder4j.main;
public class HeapSort {
/**
* 調劑為小頂堆（排序後成果為從年夜到小）
*
* @param array是待調劑的堆數組
* @param s是待調劑的數組元素的地位
* @param length是數組的長度
*
*/
public static void heapAdjustS(int[] array, int s, int length) {
int tmp = array[s];
int child = 2 * s + 1;// 左孩子結點的地位
System.out.println("待調劑結點為：array[" + s + "] = " + tmp);
while (child < length) {
// child + 1 是以後調劑結點的右孩子
// 假如有右孩子且小於左孩子，應用右孩子與結點停止比擬，不然應用左孩子
if (child + 1 < length && array[child] > array[child + 1]) {
child++;
}
System.out.println("將與子孩子 array[" + child + "] = " + array[child] + " 停止比擬");
// 假如較小的子孩子比此結點小
if (array[s] > array[child]) {
System.out.println("子孩子比其小，交流地位");
array[s] = array[child];// 把較小的子孩子向上挪動，調換以後待調劑結點
s = child;// 待調劑結點挪動到較小子孩子本來的地位
array[child] = tmp;
child = 2 * s + 1;// 持續斷定待調劑結點能否須要持續調劑
if (child >= length) {
System.out.println("沒有子孩子了，調劑停止");
} else {
System.out.println("持續與新的子孩子停止比擬");
}
// continue;
} else {
System.out.println("子孩子均比其年夜，調劑停止");
break;// 以後待調劑結點小於它的閣下孩子，不需調劑，直接加入
}
}
}
/**
* 調劑為年夜頂堆（排序後成果為從小到年夜）
*
* @param array是待調劑的堆數組
* @param s是待調劑的數組元素的地位
* @param length是數組的長度
*
*/
public static void heapAdjustB(int[] array, int s, int length) {
int tmp = array[s];
int child = 2 * s + 1;// 左孩子結點的地位
System.out.println("待調劑結點為：array[" + s + "] = " + tmp);
while (child < length) {
// child + 1 是以後調劑結點的右孩子
// 假如有右孩子且年夜於左孩子，應用右孩子與結點停止比擬，不然應用左孩子
if (child + 1 < length && array[child] < array[child + 1]) {
child++;
}
System.out.println("將與子孩子 array[" + child + "] = " + array[child] + " 停止比擬");
// 假如較年夜的子孩子比此結點年夜
if (array[s] < array[child]) {
System.out.println("子孩子比其年夜，交流地位");
array[s] = array[child];// 把較年夜的子孩子向上挪動，調換以後待調劑結點
s = child;// 待調劑結點挪動到較年夜子孩子本來的地位
array[child] = tmp;
child = 2 * s + 1;// 持續斷定待調劑結點能否須要持續調劑
if (child >= length) {
System.out.println("沒有子孩子了，調劑停止");
} else {
System.out.println("持續與新的子孩子停止比擬");
}
// continue;
} else {
System.out.println("子孩子均比其小，調劑停止");
break;// 以後待調劑結點年夜於它的閣下孩子，不需調劑，直接加入
}
}
}
/**
* 堆排序算法
*
* @param array
* @param inverse true 為倒序分列，false 為正序分列
*/
public static void heapSort(int[] array, boolean inverse) {
// 初始堆
// 最初一個有孩子的結點地位 i = (length - 1) / 2, 以此向上調劑各結點使其相符堆
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("初始堆停止");
for (int i = array.length - 1; i > 0; i--) {
// 交流堆頂元素H[0]和堆中最初一個元素
int tmp = array[i];
array[i] = array[0];
array[0] = tmp;
// 每次交流堆頂元素和堆中最初一個元素以後，都要對堆停止調劑
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 + " ");
}
}
}
運轉成果：
初始堆開端 待調劑結點為：array[3] = 97 將與子孩子 array[7] = 49 停止比擬 子孩子比其小，交流地位 沒有子孩子了，調劑停止 待調劑結點為：array[2] = 65 將與子孩子 array[5] = 13 停止比擬 子孩子比其小，交流地位 沒有子孩子了，調劑停止 待調劑結點為：array[1] = 38 將與子孩子 array[3] = 49 停止比擬 子孩子均比其年夜，調劑停止 待調劑結點為：array[0] = 49 將與子孩子 array[2] = 13 停止比擬 子孩子比其小，交流地位 持續與新的子孩子停止比擬 將與子孩子 array[6] = 27 停止比擬 子孩子比其小，交流地位 沒有子孩子了，調劑停止 初始堆停止 待調劑結點為：array[0] = 97 將與子孩子 array[2] = 27 停止比擬 子孩子比其小，交流地位 持續與新的子孩子停止比擬 將與子孩子 array[6] = 49 停止比擬 子孩子比其小，交流地位 沒有子孩子了，調劑停止 待調劑結點為：array[0] = 97 將與子孩子 array[1] = 38 停止比擬 子孩子比其小，交流地位 持續與新的子孩子停止比擬 將與子孩子 array[3] = 49 停止比擬 子孩子比其小，交流地位 沒有子孩子了，調劑停止 待調劑結點為：array[0] = 65 將與子孩子 array[1] = 49 停止比擬 子孩子比其小，交流地位 持續與新的子孩子停止比擬 將與子孩子 array[4] = 76 停止比擬 子孩子均比其年夜，調劑停止 待調劑結點為：array[0] = 76 將與子孩子 array[2] = 49 停止比擬 子孩子比其小，交流地位 沒有子孩子了，調劑停止 待調劑結點為：array[0] = 97 將與子孩子 array[1] = 65 停止比擬 子孩子比其小，交流地位 沒有子孩子了，調劑停止 待調劑結點為：array[0] = 76 將與子孩子 array[1] = 97 停止比擬 子孩子均比其年夜，調劑停止 待調劑結點為：array[0] = 97 97 76 65 49 49 38 27 13
PS：堆排序與直接拔出排序的差別
直接選擇排序中，為了從R[1..n]當選出症結字最小的記載，必需停止n-1次比擬，然後在R[2..n]當選出症結字最小的記載，又須要做n-2次比擬。現實上，前面的n-2次比擬中，有很多比擬能夠在後面的n-1次比擬中曾經做過，但因為前一趟排序時未保存這些比擬成果，所今後一趟排序時又反復履行了這些比擬操作。
堆排序可經由過程樹形構造保留部門比擬成果，可削減比擬次數。
