圖解堆排序
“程序員常用的IDEA插件：https://github.com/silently9527/ToolsetIdeaPlugin
“完全開源的淘客項(xiàng)目：https://github.com/silently9527/mall-coupons-server
“微信公眾號：貝塔學(xué)Java
前言
在上一篇中我們一起使用二叉堆實(shí)現(xiàn)了優(yōu)先級隊(duì)列，假如我們從構(gòu)建好的優(yōu)先級隊(duì)列中持續(xù)調(diào)用刪除最?。ɑ蛘咦畲螅呀Y(jié)果輸出到另一個(gè)數(shù)組中，那么就可以把數(shù)組的所有元素進(jìn)行排序，這就是本篇我們需要學(xué)習(xí)的堆排序。在看本篇之前需要先看下前一篇《原來實(shí)現(xiàn)優(yōu)先級隊(duì)列如此簡單》
堆排序的過程主要有兩個(gè)階段：
把原始數(shù)據(jù)構(gòu)造成一個(gè)有序堆（構(gòu)造堆） 從堆中按照遞減順序取出所有元素就可以得到排序結(jié)果（下沉排序）
開始之前，我們需要把上一篇中的sink()方法修改一下；
保證我們在進(jìn)行排序的時(shí)候直接使用原始的數(shù)組，無需建立一個(gè)輔助數(shù)組浪費(fèi)空間；由于我們需要?jiǎng)討B(tài)的縮小堆的大小，需要把size通過參數(shù)傳入；
其次我們數(shù)組的下標(biāo)是從0開始的，與之前的優(yōu)先級排序有些差別，對于k節(jié)點(diǎn)的左邊節(jié)點(diǎn)下標(biāo)是2k+1，右邊下標(biāo)是2k+2
private void sink(Comparable[] queue, int k, int size) {
while (2 * k + 1 < size) {
int i = 2 * k + 1;
if (i < size - 1 && less(queue[i], queue[i + 1])) {
i++;
}
if (less(queue[i], queue[k])) {
break;
}
exch(queue, i, k);
k = i;
}
}
構(gòu)造堆
把一個(gè)輸入的數(shù)組構(gòu)建成一個(gè)堆有序，我們有兩種方式：
從左向右遍歷數(shù)組，然后把調(diào)用swim()上浮操作保證指針左邊的元素都是堆有序的，就和優(yōu)先級隊(duì)列的插入過一樣 由于數(shù)組中的每個(gè)位置已經(jīng)是堆的節(jié)點(diǎn)，我們可以從右向左調(diào)用sink()下沉操作構(gòu)造堆，這個(gè)過程我們可以跳過子堆為1的元素，所以我們只需要掃描數(shù)組的一半元素。這種方式會(huì)更高效。
例如：輸入數(shù)組 a[]={8,3,6,1,4,7,2}
下沉排序
下沉是堆排序的第二個(gè)階段，我們把最大元素刪除，然后放入到堆縮小后數(shù)組中空出來的位置，當(dāng)操作完成所有的元素之后，整個(gè)數(shù)組將會(huì)是有序的
下沉排序演示過程（圖未完全畫完）：
堆排序代碼實(shí)現(xiàn)
@Override
public void sort(Comparable[] array) {
int size = array.length;
for (int k = size / 2; k >= 0; k--) {
sink(array, k, size);
}
while (size > 0) {
exch(array, 0, --size);
sink(array, 0, size);
}
}
文中所有源碼已放入到了github倉庫https://github.com/silently9527/JavaCore
最后（點(diǎn)關(guān)注，不迷路）
文中或許會(huì)存在或多或少的不足、錯(cuò)誤之處，有建議或者意見也非常歡迎大家在評論交流。
最后，寫作不易，請不要白嫖我喲，希望朋友們可以點(diǎn)贊評論關(guān)注三連，因?yàn)檫@些就是我分享的全部動(dòng)力來源??