資訊專欄INFORMATION COLUMN
摘要：一堆排序介紹來源百度百科堆排序是指利用堆積樹堆這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法，它是選擇排序的一種。
一、堆排序介紹
來源百度百科：
堆排序(Heapsort)是指利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法，它是選擇排序的一種?？梢岳脭?shù)組的特點快速定位指定索引的元素。堆分為大根堆和小根堆，是完全二叉樹。
前面我已經(jīng)有二叉樹入門的文章了，當(dāng)時講解的是二叉查找樹，那上面所說的完全二叉樹是怎么樣的一種二叉樹呢？？還有滿二叉樹又是怎么的一種二叉樹呢？？甚至還有完滿二叉樹？？
完全二叉樹： 除了最后一層之外的其他每一層都被完全填充，并且所有結(jié)點都保持向左對齊。
滿二叉樹：除了葉子結(jié)點之外的每一個結(jié)點都有兩個孩子，每一層(當(dāng)然包含最后一層)都被完全填充。
完滿二叉樹：除了葉子結(jié)點之外的每一個結(jié)點都有兩個孩子結(jié)點。
下面用圖來說話：
完全二叉樹(Complete Binary Tree)：
滿二叉樹(Perfect Binary Tree)：
完滿二叉樹(Full Binary Tree)：
參考資料：
http://www.cnblogs.com/idorax/p/6441043.html
簡單來說：堆排序是將數(shù)據(jù)看成是完全二叉樹、根據(jù)完全二叉樹的特性來進行排序的一種算法
最大堆要求節(jié)點的元素都要不小于其孩子，最小堆要求節(jié)點元素都不大于其左右孩子
那么處于最大堆的根節(jié)點的元素一定是這個堆中的最大值
這里我們討論最大堆：當(dāng)前每個父節(jié)點都大于子節(jié)點
完全二叉樹有個特性：左邊子節(jié)點位置 = 當(dāng)前父節(jié)點的兩倍 + 1，右邊子節(jié)點位置 = 當(dāng)前父節(jié)點的兩倍 + 2
二、堆排序體驗現(xiàn)在我們有一個完全二叉樹：左子樹和右子樹都符合最大堆-->父>子
但是我們會發(fā)現(xiàn)：根元素所在的數(shù)并不符合，明顯的是：1是小于7的
我們就對其進行交換，交換完之后我們會發(fā)現(xiàn)：右子樹又不符合了～
因為，右子樹變成了這樣：
最后，我們將右子數(shù)的最大值也交換到右子樹的根元素上
于是我們第一次的建堆操作就完成了！
可以發(fā)現(xiàn)的是：一次堆建立完之后，我們的最大值就在了堆的根節(jié)點上
隨后將堆頂最大值和數(shù)組最后的元素進行替換，我們就完成了一趟排序了。
接下來，剩下的數(shù)不斷進行建堆，交換就可以完成我們的堆排序了
.........建堆，交換....建堆，交換...建堆，交換...建堆，交換..
三、堆排序代碼實現(xiàn)比較當(dāng)前父節(jié)點是否大于子節(jié)點，如果大于就交換，直到一趟建堆完成～
/**
* 建堆
*
* @param arrays 看作是完全二叉樹
* @param currentRootNode 當(dāng)前父節(jié)點位置
* @param size 節(jié)點總數(shù)
*/
public static void heapify(int[] arrays, int currentRootNode, int size) {
if (currentRootNode < size) {
//左子樹和右字?jǐn)?shù)的位置
int left = 2 * currentRootNode + 1;
int right = 2 * currentRootNode + 2;
//把當(dāng)前父節(jié)點位置看成是最大的
int max = currentRootNode;
if (left < size) {
//如果比當(dāng)前根元素要大，記錄它的位置
if (arrays[max] < arrays[left]) {
max = left;
}
}
if (right < size) {
//如果比當(dāng)前根元素要大，記錄它的位置
if (arrays[max] < arrays[right]) {
max = right;
}
}
//如果最大的不是根元素位置，那么就交換
if (max != currentRootNode) {
int temp = arrays[max];
arrays[max] = arrays[currentRootNode];
arrays[currentRootNode] = temp;
//繼續(xù)比較，直到完成一次建堆
heapify(arrays, max, size);
}
}
}
值得注意的是：在上面體驗堆排序時，我們是左子樹和右子數(shù)都是已經(jīng)有父>子這么一個條件的了。
顯然，一個普通的數(shù)組并不能有這種條件(父>子)，因此，我們往往是從數(shù)組最后一個元素來進行建堆
/**
* 完成一次建堆，最大值在堆的頂部(根節(jié)點)
*/
public static void maxHeapify(int[] arrays, int size) {
// 從數(shù)組的尾部開始，直到第一個元素(角標(biāo)為0)
for (int i = size - 1; i >= 0; i--) {
heapify(arrays, i, size);
}
}
完成第一次建堆之后，我們會發(fā)現(xiàn)最大值會在數(shù)組的首位：
接下來不斷建堆，然后讓數(shù)組最后一位與當(dāng)前堆頂(數(shù)組第一位)進行交換即可排序：
for (int i = 0; i < arrays.length; i++) {
//每次建堆就可以排除一個元素了
maxHeapify(arrays, arrays.length - i);
//交換
int temp = arrays[0];
arrays[0] = arrays[(arrays.length - 1) - i];
arrays[(arrays.length - 1) - i] = temp;
}
四、總結(jié)
堆排序是比其他排序要難一點，他用到了完全二叉樹這么一個特性來進行排序，代碼實現(xiàn)上也比其他排序要復(fù)雜一點。
參考資料：
http://www.cnblogs.com/skywang12345/p/3602162.html
如果文章有錯的地方歡迎指正，大家互相交流。習(xí)慣在微信看技術(shù)文章，想要獲取更多的Java資源的同學(xué)，可以關(guān)注微信公眾號:Java3y
文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址：http://www.ezyhdfw.cn/yun/76363.html
摘要：數(shù)組就是一個簡單的線性序列，這使得元素訪問非?？焖?。堆區(qū)堆內(nèi)存用來存放創(chuàng)建的對象和數(shù)組。堆內(nèi)存中的實體不再被指向時，啟動垃圾回收機制，自動清除，這也是優(yōu)于的表現(xiàn)之一中需要程序員手動清除。 showImg(https://segmentfault.com/img/remote/1460000019264541?w=600&h=242); 第三章 方法和數(shù)組 3.1 概述 還記得我們的He...
摘要：適用于數(shù)據(jù)比較少或基本有序的情況。插入排序時間復(fù)雜度為，空間復(fù)雜度為，屬于穩(wěn)定排序。算法適用于少量數(shù)據(jù)的排序。就像下圖這樣，可以理解桶的意思下圖是整個排序過程示意圖基數(shù)排序時間復(fù)雜度為，空間復(fù)雜度為，屬于穩(wěn)定排序。 寫在前面 個人感覺：javascript對類似排序查找這樣的功能已經(jīng)有了很好的封裝，以致于當(dāng)我們想對數(shù)組排序的時候只需要調(diào)用arr.sort()方法，而查找數(shù)組元素也只需要...
摘要：前言由于寫的文章已經(jīng)是有點多了，為了自己和大家的檢索方便，于是我就做了這么一個博客導(dǎo)航。 前言 由于寫的文章已經(jīng)是有點多了，為了自己和大家的檢索方便，于是我就做了這么一個博客導(dǎo)航。 由于更新比較頻繁，因此隔一段時間才會更新目錄導(dǎo)航哦～想要獲取最新原創(chuàng)的技術(shù)文章歡迎關(guān)注我的公眾號：Java3y Java3y文章目錄導(dǎo)航 Java基礎(chǔ) 泛型就這么簡單 注解就這么簡單 Druid數(shù)據(jù)庫連接池...
閱讀 1302·2021-11-11 16:54
閱讀 936·2021-10-19 11:44
閱讀 1399·2021-09-22 15:18
閱讀 2521·2019-08-29 16:26
閱讀 3017·2019-08-29 13:57
閱讀 3159·2019-08-26 13:32
閱讀 1154·2019-08-26 11:58
閱讀 2402·2019-08-26 10:37
