您好,登錄后才能下訂單哦!
小編給大家分享一下C語言中堆排序怎么用,相信大部分人都還不怎么了解,因此分享這篇文章給大家參考一下,希望大家閱讀完這篇文章后大有收獲,下面讓我們一起去了解一下吧!
???? 堆排序(Heapsort):利用堆積樹(堆)這種數(shù)據(jù)結(jié)構(gòu)所設(shè)計的一種排序算法,它是選擇排序的一種。通過堆來進(jìn)行選擇數(shù)據(jù),需要注意的是 排升序要建大堆,排降序建小堆。
堆排序使用堆來選數(shù),效率就高了很多。
時間復(fù)雜度:
空間復(fù)雜度:
穩(wěn)定性:不穩(wěn)定
我們先創(chuàng)建一個堆排序的函數(shù):
void HeapSort(int arr[], int n);
假設(shè)我們要對下列數(shù)組來使用堆排序(升序):
int arr[] = {70, 56, 30, 25, 15, 10, 75};
根據(jù)我們之前學(xué)到的知識,數(shù)組是可以直接看作為完全二叉樹的,所以我們可以把它化為堆。此時我們就可以 "選數(shù)" (堆排序本質(zhì)上是一種選擇排序)。
第一步就是要想辦法把 arr 數(shù)組構(gòu)建成堆(這里我們先構(gòu)建成小堆)。我們介紹兩種方法,分別為向上調(diào)整算法和向下調(diào)整算法:
方法1:向上調(diào)整
通過我們之前學(xué)過的 "向上調(diào)整" ,利用插入的思路來解決。首先設(shè)計下向上調(diào)整的算法:
void Swap(HPDataType* px, HPDataType* py) { HPDataType tmp = *px; *px = *py; *py = tmp; } /* 小堆的向上調(diào)整 */ void AdjustUp(int* arr, int child) { assert(arr); // 首先根據(jù)公式計算算出父親的下標(biāo) int parent = (child - 1) / 2; // 最壞情況:調(diào)到根,child=parent 當(dāng)child為根節(jié)點(diǎn)時結(jié)束(根節(jié)點(diǎn)永遠(yuǎn)是0) while(child > 0) { if(arr[child] < arr[parent]) { // 如果孩子小于父親(不符合小堆的性質(zhì)) // 交換他們的值 Swap(&arr[child],&arr[parent]); // 傳地址 // 往上走 child = parent; parent = (child - 1) / 2; } else { // 如果孩子大于父親(符合小堆的性質(zhì)) // 跳出循環(huán) break; } } }
① 首先,通過公式計算出父親的下標(biāo),公式如下:
② 其次,設(shè)計循環(huán)部分,最壞情況為調(diào)到根,如果已經(jīng)符合大堆的條件則終止循環(huán)。
③ 進(jìn)入循環(huán)后進(jìn)行判斷,如果 child > parent,則交換它們的值,讓父親獲得孩子的值,孩子得到父親的值,從而讓它們符合大堆的性質(zhì)。
④ 交換完畢后,以便于繼續(xù)判斷,我們需要更新 child 和 parent 指向的元素,做到 "往上走"
此時,我們把數(shù)組里的元素依次調(diào)整即可。
???? 方法1:
/* 升序 */ void HeapSort(int arr[], int n) { for (int i = 1; i < n; i++) { AdjustUp(arr, i); // 傳入數(shù)組 和 child的下標(biāo) } }
我們不需要從 0 開始調(diào),從 1 開始調(diào)。所以 i 的起始值設(shè)置為 1 。此時,小堆就構(gòu)建好了。
方法2:向下調(diào)整
向下調(diào)整算法我們在堆那個章節(jié)也學(xué)過了,這里我們再來復(fù)習(xí)一下:
void SmallAjustDown(int* arr, int n, int parent) { int child = parent * 2 + 1; // 默認(rèn)為左孩子 while(child < n) { // 葉子內(nèi) // 選出左右孩子中小的那一個 if(child + 1 < n && arr[child + 1] < arr[child]) { child = child + 1; } // 如果孩子小于父親(不符合小堆的性質(zhì)) if(arr[child] < arr[parent]) { // 交換它們的值 Swap(&arr[child], &arr[parent]); // 往下走 parent = child; child = parent * 2 + 1; } else { // 如果孩子大于父親(符合小堆的性質(zhì)) // 跳出循環(huán) break; } } }
① 因為要考慮左孩子還是右孩子,我們可以定義兩個變量,分別記錄左孩子和有孩子。但是我們這里可以用更好的方法,只需要定義一個孩子即可。具體實現(xiàn)方法如下:首先創(chuàng)建 child,我們先默認(rèn)它是左孩子,利用傳進(jìn)來的 parent 根據(jù)公式計算出 child 的大?。?/p>
因為我們暫且默認(rèn)為左孩子,我們隨后進(jìn)入循環(huán)后要進(jìn)行檢查,看看是左孩子大還是右孩子大,這里我們只需要根據(jù)數(shù)組的性質(zhì),將 child + 1 即可得到右孩子的下標(biāo),從而方便我們進(jìn)行比較。比較完畢后將 child 重新賦值,拿個孩子小就將 child 給誰。
② 一共有兩個結(jié)束條件(出口),第一個結(jié)束條件是父親小于孩子就停止,第二個結(jié)束條件是chi調(diào)整到葉子。所以,循環(huán)體判斷部分根據(jù)我們分析的結(jié)束條件,如果調(diào)整到葉子就結(jié)束,我們接受了 n,也就是數(shù)組的大小,只要 child 超過數(shù)組的大小(child > n) 就結(jié)束,這是第一個出口。
③ 進(jìn)入循環(huán)后,對比左孩子和右孩子哪一個更小,child 就交付給誰。這里還要注意的是,要防止孩子不存在的情況,如果 child + 1 比 n 大,就說明孩子不存在。所以我們再寫 if 判斷條件的時候就要注意了,我們加一個 child + 1 < n 的條件限制一下:
if(child + 1 < n && arr[child + 1] < arr[child]) {...}
④ 確認(rèn)好較小的孩子后,我們就可以開始比較孩子和父親的大小了。如果孩子小于父親,就不符合小堆的性質(zhì),我們就要交換它們的值。這里我們直接調(diào)用我們剛才寫的 Swap 接口即可,這就是為什么在寫向上調(diào)整的時候要我們單獨(dú)把交換部分的代碼寫成函數(shù)的原因。
⑤ 交換完畢后,他們的值已經(jīng)互相交換好了,這時我們要改變 parent 和 child 的指向,讓它們往下走,parent = child ,child 再次根據(jù)公式算出新的 child 即可。
⑥ 設(shè)計下 if 的 else 部分,如果數(shù)組的 child 的值大于 parent 的值,說明符合小堆的性質(zhì)了, break 跳出循環(huán)即可,這是第二個出口。
向下調(diào)整算法的前提:左右子樹必須都是小堆
如果左子樹和右子樹不是小堆,怎么辦?
可以用遞歸解決,但是我們能用循環(huán)就用循環(huán)來解決:
葉子所在的子樹是不需要調(diào)的。所以,我們從倒著走的第一個非葉子結(jié)點(diǎn)的子樹開始調(diào)。
(所以我們先調(diào)整30)
為了能夠演示得更明顯,我們再給數(shù)組再加點(diǎn)數(shù)據(jù),假設(shè)我們需要對以下數(shù)組排序:
這里,我們找到了15。
…… 下標(biāo)不斷地 - - 后:
由于,從倒著走的第一個非葉子結(jié)點(diǎn)的子樹開始調(diào),即,最后一個節(jié)點(diǎn)的父親。
我們已知最后一個節(jié)點(diǎn)的下標(biāo)為:
那么,我們可以通過公式計算出他父親的下標(biāo):
???? 方法2:
/* 升序 */ void HeapSort(int arr[], int n) { for (int i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(arr, n, i); } }
? 這么寫或許可以看得更明白:
/* 升序 */ void HeapSort(int arr[], int sz) { int father = ((sz - 1) - 1) / 2; // 計算出最后一個葉子節(jié)點(diǎn)的父親 while (father >= 0) { AdjustDown(arr, sz, father); father--; } }
???? 測試堆是否創(chuàng)建好了:
我們這里選擇使用方法2。此外,我們剛才實現(xiàn)的是小堆。
#include <stdio.h> /* 交換函數(shù) */ void Swap(int* px, int* py) { int tmp = *px; *px = *py; *py = tmp; } /* 小堆下調(diào) */ void AdjustDown(int arr[], int sz, int father_idx) { int child_idx = father_idx * 2 + 1; // 計算出左孩子的值(默認(rèn)認(rèn)為左孩子大) while (child_idx < sz) { // 最壞情況:調(diào)到葉子(child >= 數(shù)組范圍時必然已經(jīng)調(diào)到葉子) if ((child_idx + 1 < sz) && (arr[child_idx + 1] < arr[child_idx])) { // 如果右孩子存在且右孩子比左孩子小 child_idx = child_idx + 1; // 讓其代表右孩子 } if (arr[child_idx] < arr[father_idx]) { // 如果孩子的值小于父親的值(大符合小堆的性質(zhì)) Swap(&arr[child_idx], &arr[father_idx]); // 交換它們的值 /* 往下走 */ father_idx = child_idx; // 更新下標(biāo) child_idx = father_idx * 2 + 1; // 計算出該節(jié)點(diǎn)路線的新父親 } else { // 如果孩子的值大于父親的值(符合小堆的性質(zhì)) break; // 終止循環(huán) } } } /* 升序 */ void HeapSort(int arr[], int sz) { /* 創(chuàng)建大堆,選出最大的數(shù) O(N) */ int father = ((sz - 1) - 1) / 2; // 計算出最后一個葉子節(jié)點(diǎn)的父親 while (father >= 0) { AdjustDown(arr, sz, father); father--; } } void HeapPrint(int arr[], int sz) { for (int i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); } int main(void) { int arr[] = {70, 56, 30, 25, 15, 10, 75, 33, 50, 69}; int sz = sizeof(arr) / sizeof(arr[0]); HeapSort(arr, sz); HeapPrint(arr, sz); return 0; }
???? 運(yùn)行結(jié)果:10 15 30 25 56 70 75 33 50 69
剛才介紹了兩種方法來構(gòu)建堆,現(xiàn)在堆已經(jīng)構(gòu)建完畢了,我們可以開始設(shè)計排序部分的算法了。
? 如果排升序,建小堆……
① 選出最小的數(shù),放到第一個位置,這很簡單,直接取頂部就可以得到最小的數(shù)。
② 但問題來了,如何選出次小的數(shù)呢?
從 15 開始,剩下的元素看作一個堆。但是這之前建立好的堆關(guān)系全部亂了!你還得重新建堆,才能選出次小的數(shù)。建堆的時間復(fù)雜度為 ,需要不斷地建堆 則用小堆的時間復(fù)雜度就是 ,這太離譜了!搞了一大圈結(jié)果居然是,還不如直接遍歷選出來的方便呢。
建小堆來排升序是完全可以的,但是效率太低!完全沒有體現(xiàn)出你用堆的優(yōu)勢!
? 解決方法:使用大堆來排升序!
???? 我們剛才已經(jīng)實現(xiàn)好小堆了,根據(jù)上一節(jié)學(xué)到的知識,小堆要變成大堆,直接把剛才的代碼的 "<" 改成 ">" 即可:
#include <stdio.h> /* 交換函數(shù) */ void Swap(int* px, int* py) { int tmp = *px; *px = *py; *py = tmp; } /* 大堆下調(diào) */ void AdjustDown(int arr[], int sz, int father_idx) { int child_idx = father_idx * 2 + 1; // 計算出左孩子的值(默認(rèn)認(rèn)為左孩子大) while (child_idx < sz) { // 最壞情況:調(diào)到葉子(child >= 數(shù)組范圍時必然已經(jīng)調(diào)到葉子) if ((child_idx + 1 < sz) && (arr[child_idx + 1] > arr[child_idx])) { // 如果右孩子存在且右孩子比左孩子大 child_idx = child_idx + 1; // 讓其代表右孩子 } if (arr[child_idx] > arr[father_idx]) { // 如果孩子的值大于父親的值(不符合大堆的性質(zhì)) Swap(&arr[child_idx], &arr[father_idx]); // 交換它們的值 /* 往下走 */ father_idx = child_idx; // 更新下標(biāo) child_idx = father_idx * 2 + 1; // 計算出該節(jié)點(diǎn)路線的新父親 } else { // 如果孩子的值小于父親的值(符合大堆的性質(zhì)) break; // 終止循環(huán) } } } /* 升序 */ void HeapSort(int arr[], int sz) { /* 創(chuàng)建大堆,選出最大的數(shù) O(N) */ int father = ((sz - 1) - 1) / 2; // 計算出最后一個葉子節(jié)點(diǎn)的父親 while (father >= 0) { AdjustDown(arr, sz, father); father--; } } void PrintArray(int arr[], int sz) { for (int i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); } int main(void) { int arr[] = {70, 56, 30, 25, 15, 10, 75, 33, 50, 69}; int sz = sizeof(arr) / sizeof(arr[0]); HeapSort(arr, sz); PrintArray(arr, sz); return 0; }
???? 運(yùn)行結(jié)果:75 69 70 50 56 10 30 33 25 15
???? 現(xiàn)在改成了大堆,我們要排升序,我們可以讓堆頂數(shù)和最后的數(shù)進(jìn)行交換:
這并不會帶來堆結(jié)構(gòu)的破壞!我們把75不看作堆的一部分即可。再進(jìn)行向下調(diào)整,就可以找到次小的數(shù)了。此時時間復(fù)雜度為
???? 步驟總結(jié):
① 建大堆,選出最大的數(shù)。
② 最大的數(shù)跟最后一個數(shù)交換。
③ 如何選出次大的數(shù)呢?把最后一個數(shù)不看作堆里面,進(jìn)行向下調(diào)整。
???? 代碼實現(xiàn)(用 while):
/* 堆排序 - 升序 */ void HeapSort(int arr[], int sz) { /* 創(chuàng)建大堆,選出最大的數(shù) O(N) */ int father = ((sz - 1) - 1) / 2; // 計算出最后一個葉子節(jié)點(diǎn)的父親 while (father >= 0) { AdjustDown(arr, sz, father); father--; } /* 依次選數(shù),調(diào)堆 O(N * logN) */ int end = sz - 1; while (end > 0) { Swap(&arr[0], &arr[end]); // 最大的數(shù)跟最后一個數(shù)交換 AdjustDown(arr, end, 0); // 調(diào)堆,選出次大的數(shù) end--; } }
???? 代碼實現(xiàn)(用 for):
void HeapSort(int arr[], int sz) { /* 建堆 */ for (int father = (sz - 1 - 1) / 2; father >= 0; father--) { AdjustDown(arr, sz, father); } /* 排序 */ for (int end = sz - 1; end > 0; end--) { Swap(&arr[0], &arr[end]); // 最大的數(shù)跟最后一個數(shù)交換 AdjustDown(arr, end, 0); // 調(diào)堆,選出次大的數(shù) } }
(排升序要建大堆,排降序建小堆)
???? 升序:使用大堆
#define _CRT_SECURE_NO_WARNINGS 1 #include <stdio.h> void Swap(int* pa, int* pb) { int tmp = *pa; *pa = *pb; *pb = tmp; } void AdjustDown(int arr[], int sz, int father) { int child = father * 2 + 1; while (child < sz) { if (child + 1 < sz && arr[child + 1] > arr[child]) { child += 1; } if (arr[child] > arr[father]) { Swap(&arr[child], &arr[father]); father = child; child = father * 2 + 1; } else { break; } } } /* 堆排序 - 升序 */ void HeapSort(int arr[], int sz) { /* 創(chuàng)建大堆,選出最大的數(shù) O(N) */ int father = ((sz - 1) - 1) / 2; // 計算出最后一個葉子節(jié)點(diǎn)的父親 while (father >= 0) { AdjustDown(arr, sz, father); father--; } /* 依次選數(shù),調(diào)堆 O(N * logN) */ int end = sz - 1; while (end > 0) { Swap(&arr[0], &arr[end]); // 最大的數(shù)跟最后一個數(shù)交換 AdjustDown(arr, end, 0); // 調(diào)堆,選出次大的數(shù) end--; } } void HeapPrint(int arr[], int sz) { int i = 0; for (i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); } int main(void) { int arr[] = { 70, 56, 30, 25, 15, 10, 75, 33, 50, 69 }; int sz = sizeof(arr) / sizeof(arr[0]); printf("排序前: "); HeapPrint(arr, sz); HeapSort(arr, sz); printf("排序后: "); HeapPrint(arr, sz); return 0; }
???? 運(yùn)行結(jié)果:
? 如果要排降序呢?使用小堆即可!
???? 降序:使用小堆
#include <stdio.h> /* 交換函數(shù) */ void Swap(int* px, int* py) { int tmp = *px; *px = *py; *py = tmp; } /* 小堆下調(diào) */ void AdjustDown(int arr[], int sz, int father_idx) { int child_idx = father_idx * 2 + 1; // 計算出左孩子的值(默認(rèn)認(rèn)為左孩子大) while (child_idx < sz) { // 最壞情況:調(diào)到葉子(child >= 數(shù)組范圍時必然已經(jīng)調(diào)到葉子) if ((child_idx + 1 < sz) && (arr[child_idx + 1] < arr[child_idx])) { // 如果右孩子存在且右孩子比左孩子小 child_idx = child_idx + 1; // 讓其代表右孩子 } if (arr[child_idx] < arr[father_idx]) { // 如果孩子的值小于父親的值(不符合小堆的性質(zhì)) Swap(&arr[child_idx], &arr[father_idx]); // 交換它們的值 /* 往下走 */ father_idx = child_idx; // 更新下標(biāo) child_idx = father_idx * 2 + 1; // 計算出該節(jié)點(diǎn)路線的新父親 } else { // 如果孩子的值大于父親的值(符合小堆的性質(zhì)) break; // 終止循環(huán) } } } /* 堆排序 - 降序 */ void HeapSort(int arr[], int sz) { /* 創(chuàng)建大堆,選出最大的數(shù) O(N) */ int father = ((sz - 1) - 1) / 2; // 計算出最后一個葉子節(jié)點(diǎn)的父親 while (father >= 0) { AdjustDown(arr, sz, father); father--; } /* 依次選數(shù),調(diào)堆 O(N * logN) */ int end = sz - 1; while (end > 0) { Swap(&arr[0], &arr[end]); // 最大的數(shù)跟最后一個數(shù)交換 AdjustDown(arr, end, 0); // 調(diào)堆,選出次小的數(shù) end--; } } void PrintArray(int arr[], int sz) { for (int i = 0; i < sz; i++) { printf("%d ", arr[i]); } printf("\n"); } int main(void) { int arr[] = { 70, 56, 30, 25, 15, 10, 75, 33, 50, 69 }; int sz = sizeof(arr) / sizeof(arr[0]); printf("排序前: "); PrintArray(arr, sz); HeapSort(arr, sz); printf("排序后: "); PrintArray(arr, sz); return 0; }
???? 運(yùn)行結(jié)果:
因為堆是完全二叉樹,而滿二叉樹也是完全二叉樹。此處為了簡化,將采用滿二叉樹來證明。(時間復(fù)雜度本來看的就是近似值,所以多幾個節(jié)點(diǎn)不會影響最終結(jié)果):
假設(shè)樹的高度為:
第 層:個節(jié)點(diǎn),需要向下移動層
第層:個節(jié)點(diǎn),需要向下移動層
第 層:個節(jié)點(diǎn),需要向下移動層
第層:個節(jié)點(diǎn),需要向下移動 層
……
第 層: 個節(jié)點(diǎn),需要向下移動 層
則需要移動節(jié)點(diǎn)總的移動步數(shù)為:
①
②
② - ① 錯位相減:
因此,建堆的時間復(fù)雜度為
以上是“C語言中堆排序怎么用”這篇文章的所有內(nèi)容,感謝各位的閱讀!相信大家都有了一定的了解,希望分享的內(nèi)容對大家有所幫助,如果還想學(xué)習(xí)更多知識,歡迎關(guān)注億速云行業(yè)資訊頻道!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場,如果涉及侵權(quán)請聯(lián)系站長郵箱:is@yisu.com進(jìn)行舉報,并提供相關(guān)證據(jù),一經(jīng)查實,將立刻刪除涉嫌侵權(quán)內(nèi)容。