堆排序

堆排序基于一種常見的**[[二叉樹]]結(jié)構(gòu)**：堆

我們前面講到選擇排序，它在待排序的n個(gè)記錄中選擇一個(gè)最小的記錄需要比較n一1次。本來這也可以理解，查找第一個(gè)數(shù)據(jù)需要比較這么多次是正常的，否則無法知道它是最小的記錄。
可惜的是，這樣的操作并沒有把每一趟的比較結(jié)果保存下來，在后一趟的比較中，有許多比較在前一趟已經(jīng)做過了，但由于前一趟排序時(shí)未保存這些比較結(jié)果，所以后一趟排序時(shí)又重復(fù)執(zhí)行了這些比較操作，因而記錄的比較次數(shù)較多。

那么我們有什么辦法可以用來解決這樣的重復(fù)比較的問題呢？

那么堆排序就由此而生了。簡單來說，堆的性質(zhì)包括如下幾點(diǎn)：

堆（Heap）是一種特殊的樹形數(shù)據(jù)結(jié)構(gòu)，通常用作優(yōu)先[[隊(duì)列]]。堆排序算法利用了堆的性質(zhì)來實(shí)現(xiàn)排序。堆的性質(zhì)總結(jié)如下：

1. 完全二叉樹：堆是一種完全二叉樹（Complete Binary Tree），即除了最后一層外，每一層的節(jié)點(diǎn)都是滿的，且最后一層的節(jié)點(diǎn)從左到右依次排列。
2. 堆的有序性：
   • 大頂堆（Max-Heap）：對(duì)于每一個(gè)節(jié)點(diǎn) i，都滿足 A[i] ≥ A[2i + 1] 且 A[i] ≥ A[2i + 2]（如果子節(jié)點(diǎn)存在）。即，父節(jié)點(diǎn)的值總是大于或等于其子節(jié)點(diǎn)的值。
   • 小頂堆（Min-Heap）：對(duì)于每一個(gè)節(jié)點(diǎn) i，都滿足 A[i] ≤ A[2i + 1] 且 A[i] ≤ A[2i + 2]（如果子節(jié)點(diǎn)存在）。即，父節(jié)點(diǎn)的值總是小于或等于其子節(jié)點(diǎn)的值。
3. 堆的高度：一個(gè)包含 n 個(gè)節(jié)點(diǎn)的堆的高度為 O(log n)。因?yàn)槎咽峭耆鏄?#xff0c;樹的高度和節(jié)點(diǎn)數(shù)量的對(duì)數(shù)成正比。

根據(jù)堆的有序性和完全二叉樹的性質(zhì)，我們得知將其用在排序上是可行的，并且還能夠有效減少重復(fù)比較的次數(shù)，這何樂而不為呢？

1964年，Floyd和Williams發(fā)明了堆這種數(shù)據(jù)結(jié)構(gòu)，同時(shí)也發(fā)明了堆排序這種算法。

算法思想

鑒于堆的有序性，我們在進(jìn)行堆排序時(shí)首先要構(gòu)建一個(gè)大頂堆或者小頂堆，這里為了方便計(jì)算，我們統(tǒng)一為大頂堆。在大頂堆的性質(zhì)下，可能會(huì)有人疑問：既然這個(gè)堆已經(jīng)滿足了有序性，那還需要排序什么呢？直接返回不就行了嗎？其實(shí)不然。我們所知道的有序性的堆只是針對(duì)子節(jié)點(diǎn)與父節(jié)點(diǎn)之間的大小關(guān)系，例如以下堆：

我們可以看到，它確實(shí)滿足大頂堆的性質(zhì)：父節(jié)點(diǎn)永遠(yuǎn)大于子節(jié)點(diǎn)。但是當(dāng)我們根據(jù)[[二叉樹]]的遍歷來進(jìn)行輸出時(shí)，會(huì)發(fā)現(xiàn)同一個(gè)父節(jié)點(diǎn)的子節(jié)點(diǎn)之間以及其中一個(gè)子節(jié)點(diǎn)的子節(jié)點(diǎn)實(shí)際上是無序的，例如60和10，它們之間是大于的關(guān)系；而60的子節(jié)點(diǎn)又都比10大，那么在遍歷的時(shí)候，自然就不有序了。

所以堆實(shí)際上并不是完全有序的，而我們使用堆排序這個(gè)算法，也并非是根據(jù)這樣的特征來進(jìn)行的。我們直接看它的算法步驟：

1. 首先建立大頂堆，然后將堆頂?shù)脑厝〕?#xff0c;作為最大值，與數(shù)組尾部的元素交換，并維持殘余堆的性質(zhì)（也就是將剩余n-1個(gè)元素繼續(xù)構(gòu)成一個(gè)堆）；
2. 之后將堆頂?shù)脑厝〕?#xff0c;作為次大值，與數(shù)組倒數(shù)第二位元素交換，并維持殘余堆的性質(zhì)；
3. 以此類推，在第n-1次操作后，整個(gè)數(shù)組就完成了排序。

我們可以看到，實(shí)際上堆排序的核心思想就是將第一個(gè)根節(jié)點(diǎn)（最大值）與數(shù)組末尾的元素來進(jìn)行交換（目的是為了構(gòu)建無需新開辟空間就能直接構(gòu)建有序數(shù)組，末尾元素被交換后也不會(huì)影響大頂堆的重新構(gòu)建），然后重新構(gòu)造堆，那么此時(shí)的第二個(gè)根節(jié)點(diǎn)就僅次于第一個(gè)根節(jié)點(diǎn)的大小，這么以此類推，最終將所有節(jié)點(diǎn)根據(jù)大、次大、第三大的順序排序在數(shù)組中，那么也就成功構(gòu)建出了有序的數(shù)組。

C語言代碼分析

void AdjustDown(HPDataType* a, int n,int parent)//向下調(diào)整算法
{int child = parent * 2 + 1;while (child < n){//選擇左右孩子中大的那一個(gè)if (child+1 < n && a[child+1] > a[child])//如果右孩子存在并且右孩子大于左孩子{++child;}if (a[child] > a[parent])//如果孩子大于父親{Swap(&a[child] , &a[parent]);parent = child;child = parent * 2 + 1;}else//如果孩子小于父親{break;}}
}void HeapSort(int* a, int n)
{/*for (int i = 1; i < n; i++){AdjustUp(a, i);}*/for (int i = (n - 1 - 1) / 2; i >= 0; i++)//從最后一個(gè)非葉子節(jié)點(diǎn)開始調(diào)整{AdjustDown(a, n, i);}int end = n-1;while (end > 0)//每次將堆頂元素與最后一個(gè)元素交換，然后調(diào)整堆{Swap(&a[end], &a[0]);AdjustDown(a, end, 0);end--;}
}

時(shí)間復(fù)雜度

我們發(fā)現(xiàn)堆的算法實(shí)際上是基于[[二叉樹]]排序的，并且在最壞情況和最好情況下的堆排序都是同一量級(jí)的操作，所以我們得出其時(shí)間復(fù)雜度為：O(n logn)

穩(wěn)定性

鑒于堆排序會(huì)改變前后元素的相對(duì)位置，所以：不穩(wěn)定