title: 算法與數(shù)據(jù)結(jié)構(gòu)(六)：堆排序
tags: [算法與數(shù)據(jù)結(jié)構(gòu), C語(yǔ)言, 堆排序]
date: 2019-03-31 12:32:29
categories: 算法與數(shù)據(jù)結(jié)構(gòu)
keywords: 算法與數(shù)據(jù)結(jié)構(gòu), C語(yǔ)言, 堆排序
上一次說(shuō)到了3種基本的排序算法，三種基本的排序算法時(shí)間復(fù)雜度都是O(n^2)拍嵌，雖然比較簡(jiǎn)單遭赂，但是效率相對(duì)較差，因此后續(xù)有許多相應(yīng)的改進(jìn)算法横辆，這次主要說(shuō)說(shuō)堆排序算法撇他。
堆排序算法是對(duì)選擇排序的一種優(yōu)化。
那么什么是堆呢狈蚤？堆是一種樹(shù)形結(jié)構(gòu)困肩。在維基百科上的定義是這樣的“給定堆中任意節(jié)點(diǎn) P 和 C，若 P 是 C 的母節(jié)點(diǎn)脆侮，那么 P 的值會(huì)小于等于（或大于等于） C 的值”锌畸。
這句話通俗一點(diǎn)就是，樹(shù)的根節(jié)點(diǎn)需要大于（小于）它的孩子節(jié)點(diǎn)靖避，而每個(gè)左右子樹(shù)都滿足這個(gè)條件潭枣。當(dāng)樹(shù)的根節(jié)點(diǎn)大于它的左右孩子節(jié)點(diǎn)時(shí)稱為大頂推比默，否則稱為小頂堆。
排序算法的思路是這樣的盆犁，首先將序列中的元素組織成一個(gè)大頂堆命咐，將樹(shù)的根節(jié)點(diǎn)放到序列的最后面，然后將剩余的元素再組織成一個(gè)大頂堆谐岁，然后放到倒數(shù)第二個(gè)位置醋奠，以此類(lèi)推。
先假定它們的對(duì)應(yīng)關(guān)系如下圖所示:
我們從樹(shù)的最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始伊佃，從這個(gè)子樹(shù)中選擇最大的一個(gè)數(shù)窜司，將它交換到子樹(shù)的根節(jié)點(diǎn)，也就是如下圖所示
接著再?gòu)暮笸安檎蚁乱粋€(gè)非葉子節(jié)點(diǎn)
經(jīng)過(guò)這樣一輪航揉，一直調(diào)整到樹(shù)的根節(jié)點(diǎn)例证，讓后將根節(jié)點(diǎn)放到序列的最后一個(gè)元素，接著再將剩余元素重新組織為一個(gè)新的堆迷捧，直到所有元素都完成排序
現(xiàn)在已經(jīng)對(duì)堆排序的基本思路有了一定的了解织咧，在寫(xiě)代碼之前需要建立樹(shù)節(jié)點(diǎn)與它在序列中的相關(guān)位置做一個(gè)對(duì)應(yīng)關(guān)系，假設(shè)一個(gè)非葉子節(jié)點(diǎn)在序列中的位置為n漠秋，那么它的兩個(gè)子節(jié)點(diǎn)分別是2n + 1與 2n + 2笙蒙。而且小于n的一定是位于n前方的非葉子節(jié)點(diǎn)，所以在調(diào)整堆時(shí)庆锦，從n開(kāi)始一直到0捅位，前面的一定是非葉子節(jié)點(diǎn)，根據(jù)這點(diǎn)可以寫(xiě)出這樣的代碼
void HeapSort(int a[], int nLength)
{
//從最后一個(gè)非葉子節(jié)點(diǎn)開(kāi)始調(diào)整
for (int n = nLength / 2 - 1; n >= 0; n--)
{
HeapAdjust(a, n, nLength);
}
for (int n = nLength - 1; n > 0; n--)
{
//取堆頂與最后一個(gè)葉子節(jié)點(diǎn)互換
int tmp = a[0];
a[0] = a[n];
a[n] = tmp;
//調(diào)整剩余堆
HeapAdjust(a, 0, n);
}
}
上述代碼首先取最后一個(gè)葉子節(jié)點(diǎn)搂抒，對(duì)所有非葉子節(jié)點(diǎn)進(jìn)行調(diào)整艇搀，得到堆頂?shù)淖畲笤亍Ｈ缓髮⒆畲笤嘏c序列最后一個(gè)做交換求晶，接著使用循環(huán)焰雕，對(duì)序列中剩余元素進(jìn)行同樣的操作。
調(diào)整堆時(shí)芳杏，首先比較子樹(shù)的根節(jié)點(diǎn)與它下面的所有子節(jié)點(diǎn)矩屁，并保存最大數(shù)的位置，然后將最大數(shù)與根節(jié)點(diǎn)的數(shù)進(jìn)行交換爵赵，這樣一直進(jìn)行吝秕，直到完成了堆根節(jié)點(diǎn)的交換。
void HeapAdjust(int a[], int nIdx, int nLength)
{
int child = 0; //child 保存當(dāng)前最大數(shù)的下標(biāo)
while (2 * nIdx + 1 < nLength)
{
child = 2 * nIdx + 1;
//先找子節(jié)點(diǎn)的最大值(保證存在右節(jié)點(diǎn)的情況下)
if (child < nLength - 1 && a[child] < a[child + 1])
{
child++;
}
if (a[nIdx] < a[child])
{
int tmp = a[nIdx];
a[nIdx] = a[child];
a[child] = tmp;
}else
{
break;
}
//如果進(jìn)行了交換空幻，為了防止對(duì)子節(jié)點(diǎn)對(duì)應(yīng)子樹(shù)的破壞烁峭，要對(duì)子樹(shù)也進(jìn)行調(diào)整
nIdx = child;
}
}
從算法上來(lái)看，它循環(huán)的次數(shù)與堆的深度有關(guān)秕铛，而二叉樹(shù)的深度應(yīng)該是log2(n) 向下取整约郁，所以調(diào)整的時(shí)候需要進(jìn)行l(wèi)og2(n)次調(diào)整耘柱，而外層需要從0一直到n - 1的位置每次都需要重組堆并進(jìn)行調(diào)整，所以它的時(shí)間復(fù)雜度應(yīng)該為O(nlogn), 它在效率上比選擇排序要高棍现，它的速度主要體現(xiàn)在每次查找選擇最大的數(shù)這個(gè)方面。
<hr />
