wordpress底部footerseo搜索引擎優(yōu)化工資
堆排序
堆排序基于一種常見的**[[二叉樹]]結(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é)如下:
- 完全二叉樹:堆是一種完全二叉樹(Complete Binary Tree),即除了最后一層外,每一層的節(jié)點(diǎn)都是滿的,且最后一層的節(jié)點(diǎn)從左到右依次排列。
- 堆的有序性:
- 大頂堆(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)的值。
- 大頂堆(Max-Heap):對(duì)于每一個(gè)節(jié)點(diǎn)
- 堆的高度:一個(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)行的。我們直接看它的算法步驟:
- 首先建立大頂堆,然后將堆頂?shù)脑厝〕?#xff0c;作為最大值,與數(shù)組尾部的元素交換,并維持殘余堆的性質(zhì)(也就是將剩余n-1個(gè)元素繼續(xù)構(gòu)成一個(gè)堆);
- 之后將堆頂?shù)脑厝〕?#xff0c;作為次大值,與數(shù)組倒數(shù)第二位元素交換,并維持殘余堆的性質(zhì);
- 以此類推,在第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)定