畢業(yè)久了涨享，越是基礎(chǔ)的東西忘得越徹底，最近也是趁著有時(shí)間仆百，趕緊將這些補(bǔ)一補(bǔ)厕隧。說到堆排序，是這些排序算法中最后一個(gè)重新理解的算法俄周，究其原因吁讨，應(yīng)該是其實(shí)現(xiàn)的復(fù)雜要高于其他幾個(gè)算法。
堆排序的結(jié)構(gòu)形態(tài)是用一個(gè)數(shù)組實(shí)現(xiàn)了一個(gè)二叉樹栈源，堆分為最大堆和最小堆兩種挡爵，最大堆指的是該二叉樹的任意一個(gè)父節(jié)點(diǎn)都比其相連的子節(jié)點(diǎn)大，最小堆則反之甚垦。對(duì)于最大堆來說茶鹃，其根節(jié)點(diǎn)就是整個(gè)堆的最大值。
那么對(duì)于堆排序算法來說艰亮，主要做的是兩件事闭翩，首先是建堆，之后可以通過堆來依次獲取大小有序的數(shù)值迄埃，每取一個(gè)值都需要重新調(diào)整堆來保持堆的正確性疗韵。
建堆過程稍微復(fù)雜一些，以最大堆為例侄非，首先【倒序遍歷】含有子節(jié)點(diǎn)的節(jié)點(diǎn)蕉汪，【比較】其值與子節(jié)點(diǎn)的值，如果子節(jié)點(diǎn)的值更大的話逞怨，則該節(jié)點(diǎn)的值與其子節(jié)點(diǎn)的值進(jìn)行【交換】者疤。交換完成后，需要從子節(jié)點(diǎn)的位置繼續(xù)判斷其子節(jié)點(diǎn)是否比其大叠赦，如果是的話也進(jìn)行交換驹马，這樣依次【向下傳遞調(diào)整】，直到子節(jié)點(diǎn)不比父節(jié)點(diǎn)大或者已經(jīng)到達(dá)葉子節(jié)點(diǎn)為止。
對(duì)于關(guān)鍵步驟已經(jīng)通過【】標(biāo)注出來了糯累，整個(gè)建堆過程有點(diǎn)類似冒泡排序在二叉樹上面的實(shí)現(xiàn)算利。完成以上步驟就可以獲得一個(gè)最大堆。
之后的步驟是獲取排序結(jié)果泳姐，代碼在實(shí)現(xiàn)的時(shí)候比較有意思了效拭，首先取出堆頂?shù)臄?shù)，讓其與數(shù)組最后一個(gè)數(shù)進(jìn)行交換胖秒，之后我們將數(shù)組最后一個(gè)數(shù)從堆里面排除出去允耿，之后從根節(jié)點(diǎn)開始，對(duì)堆做一次【向下傳遞調(diào)整】操作扒怖，那么我們最大值就跑數(shù)組最后面去了；第二次业稼，我們?cè)偃《秧數(shù)臄?shù)盗痒，讓其與數(shù)組最后第二個(gè)數(shù)進(jìn)行交換，之后我們將數(shù)組最后兩個(gè)數(shù)從堆里面排除出去低散，之后從根節(jié)點(diǎn)開始俯邓，對(duì)堆做一次【向下傳遞調(diào)整】操作。這樣一次進(jìn)行取數(shù)熔号、交換稽鞭、跳轉(zhuǎn)的操作，總共進(jìn)行N-1次后引镊，我們會(huì)發(fā)現(xiàn)我們的數(shù)組已經(jīng)以一個(gè)從小到大的進(jìn)行排序了朦蕴。這就是堆排序的整個(gè)過程。
c++代碼實(shí)現(xiàn)如下
// 最大堆排序 -- 獲取從小到大排序的結(jié)果
#include <iostream>
using namespace std;
void swep(int i, int j, int *unsortArray) {
int temp = unsortArray[i];
unsortArray[i] = unsortArray[j];
unsortArray[j] = temp;
}
// 調(diào)整節(jié)點(diǎn)
void adjustCurrent(int index, int* unsortArray, int size) {
int indexSon1 = index * 2 + 1;
int indexSon2 = index * 2 + 2;
bool hasNodeSon1 = (indexSon1 < size); //有第一個(gè)子節(jié)點(diǎn)
bool hasNodeSon2 = (indexSon2 < size); //有第二個(gè)子節(jié)點(diǎn)
if (!hasNodeSon1)
{
//沒有子節(jié)點(diǎn)不做處理
return;
}
if (unsortArray[index] < unsortArray[indexSon1]
|| (hasNodeSon2 && unsortArray[index] < unsortArray[indexSon2]))
{
int witchSweped = 1;
if (hasNodeSon2)
{
//判斷兩個(gè)子節(jié)點(diǎn)中最大的是哪個(gè)
if (unsortArray[indexSon1] > unsortArray[indexSon2])
{
swep(indexSon1, index, unsortArray);
} else {
swep(indexSon2, index, unsortArray);
witchSweped = 2;
}
}
else {
swep(indexSon1, index, unsortArray);
}
//向下傳遞調(diào)整
adjustCurrent(index * 2 + witchSweped, unsortArray, size);
}
}
void heapSort(int *unsortArray, int size) {
// 建堆
for (int i = size/2 - 1; i >= 0; --i)
{
//當(dāng)前節(jié)點(diǎn)調(diào)整
adjustCurrent(i, unsortArray, size);
}
// 通過堆獲取排序結(jié)果
int currentIndex = size - 1;
while(currentIndex) {
swep(currentIndex, 0, unsortArray);
adjustCurrent(0, unsortArray, currentIndex);
currentIndex --;
}
}
int main() {
int unsortArray[] = {9,8,7,6,5,4,3,2,1};
int size = sizeof(unsortArray)/sizeof(int);
cout<<"before sort"<<endl;
for (int i = 0; i < size; ++i)
{
cout<<unsortArray[i]<<" ";
}
cout<<endl;
heapSort(unsortArray, size);
cout<<"after sort"<<endl;
for (int i = 0; i < size; ++i)
{
cout<<unsortArray[i]<<" ";
}
cout<<endl;
return 0;
}
