C語言植物大戰(zhàn)數(shù)據(jù)結構堆排序圖文示例
“大弦嘈嘈如急雨,小弦切切如私語”“嘈嘈切切錯雜彈,大珠小珠落玉盤”
C語言朱武大戰(zhàn)數(shù)據(jù)結構專欄
C語言植物大戰(zhàn)數(shù)據(jù)結構快速排序圖文示例
C語言植物大戰(zhàn)數(shù)據(jù)結構希爾排序算法
C語言植物大戰(zhàn)數(shù)據(jù)結構二叉樹遞歸
TOP.堆排序前言
什么是堆排序?假如給你下面的代碼讓你完善堆排序,你會怎么寫?你會怎么排?
void HeapSort(int* a, int n) { } int main() { int arr[] = { 4,2,7,8,5,1,0,6 }; int sz = sizeof(arr) / sizoef(arr[0]); HeapSort(arr, sz); return 0; }
堆排序就是利用堆這個數(shù)據(jù)結構,對一組數(shù)據(jù)進行排序。
所以說,堆排序整體分兩步完成。
第一步,建堆
第二步,進行排序
注意:以下代碼針對的是對一組 數(shù)據(jù) 排升序
一、向下調(diào)整堆排序
對的,向下調(diào)整方法,是最優(yōu)秀的堆排序。
不是太想介紹那種向上調(diào)整拉胯的堆排序,我們經(jīng)常用的是這種優(yōu)秀的向下排序。
二者區(qū)別在于建堆的方法不同。一個是向下建堆O(N),一個是向上建堆O(N*logN)。
具體證明用到了高中 簡單的數(shù)列公式。
1.向下調(diào)整建堆
建堆的技巧
向下建堆也有兩種情況。
1.建大堆
2.建小堆
那么到底建大堆還是小堆呢?
解釋:建堆在于你是想要排升序,還是排降序。假如建的大堆,因為堆頂?shù)臄?shù)是最大的,在我們對堆 向下調(diào)整排序時,這時候每次都需要把最大的交換到堆底。所以導致最后堆的順序是升序。
建大堆前
建大堆后
向下調(diào)整排序后
此時數(shù)組就有序了。
結論:實質(zhì)是在數(shù)組上建堆。排升序建大堆,排降序建小堆。
建堆思路代碼
思路:
因為葉子結點本身就是一個大堆,所以從最后一個葉子結點的父親結點開始進行向下建堆。
這樣就能夠保證每次建的堆都是大堆。
注意:
1.注意循環(huán)結束條件,和if語句里的邊界問題child + 1 < n
2.注意完全二叉樹父子關系公式
#include <stdio.h> //交換 void swap(int* x, int* y) { int t = 0; t = *x; *x = *y; *y = t; } //向下調(diào)整 void AdjustDown(int* a, int n, int root) { int parent = root; int child = parent * 2 + 1; while (child < n) { //每次調(diào)整都需要從左右兩邊選出孩子最大的那個 //假設坐孩子較大,選出左右孩子大的那個 if (child + 1 < n && a[child + 1] > a[child]) { ++child; } //開始調(diào)整。 if (a[child] > a[parent]) { swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } //不滿足就跳出,開始下次for循環(huán)調(diào)整。 else { break; } } } void HeapSort(int* a, int n) { //向下調(diào)整建堆 int i = 0; for (i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } } int main() { int arr[] = { 4,2,7,8,5,1,0,6 }; int sz = sizeof(arr) / sizeof(arr[0]); HeapSort(arr, sz); return 0; }
2.向下調(diào)整排序
調(diào)整思路
1.從堆底依次 和 堆頂?shù)臄?shù)據(jù)進行交換。
2.對交換后的 堆頂?shù)闹?進行向下調(diào)整。向下調(diào)整時請無視交換到堆底那個最大的值。
3.繼續(xù)循環(huán)第一步和第二步,直到到正數(shù)第二個數(shù)結束。
排序整體代碼
void swap(int* x, int* y) { int t = 0; t = *x; *x = *y; *y = t; } void AdjustDown(int* a, int n, int root) { int parent = root; int child = parent * 2 + 1; while (child < n) { //每次調(diào)整都需要從左右兩邊選出孩子最大的那個 //假設坐孩子較大,選出左右孩子大的那個 if (child + 1 < n && a[child + 1] > a[child]) { ++child; } //開始調(diào)整。 if (a[child] > a[parent]) { swap(&a[child], &a[parent]); parent = child; child = parent * 2 + 1; } //不滿足就跳出,開始下次for循環(huán)調(diào)整。 else { break; } } } void HeapSort(int* a, int n) { //向下調(diào)整建堆 int i = 0; for (i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); } //向下調(diào)整排序 int end = 0; for (end = n-1; end > 0; end--) { swap(&a[0], &a[end]); //向下調(diào)整時無視最大的那個值,所以end是n-1。 AdjustDown(a, end, 0); } } int main() { int arr[] = { 4,2,7,8,5,1,0,6 }; int sz = sizeof(arr) / sizeof(arr[0]); HeapSort(arr, sz); return 0; }
3.時間復雜度(難點)
向下建堆O(N)
//向下調(diào)整建堆 int i = 0; for (i = (n - 1 - 1) / 2; i >= 0; i--) { AdjustDown(a, n, i); }
很多人的誤區(qū)在于他的時間復雜度是N*Log2N。這是錯誤的。
時間復雜度的計算是看思想,而不是看循環(huán)猜測。
當是滿二叉樹,在最壞的情況下,除了最后一層,上面所有層都需要進行向下調(diào)整。
最壞情況下的調(diào)整次數(shù) = 每層數(shù)據(jù)個數(shù) * 向下調(diào)整次數(shù)
第一層向下調(diào)整次數(shù)是h-1,節(jié)點個數(shù)是21-1
第二層向下調(diào)整次數(shù)是h-2, 節(jié)點個數(shù)是22-1
第h-1層向下調(diào)整次數(shù)是1,節(jié)點個數(shù)是2h-1-1
所以總的調(diào)整次數(shù)為n:n = 20*(h-1) + 21 *(h-2)+… + 2h-1-1 *(1)
根據(jù)高中錯位相減得到 n = 1−h+21+22+…+2h−2+2h−1
由等比數(shù)列前n項和得到 n = 2h−h−1
由二叉樹性質(zhì)N=2h−1和 h = log2(N+1) 得到 n=N−log2?(N+1)
大O漸進表示法為n= O(N)
向下調(diào)整(N*LogN)
需要向下調(diào)整n-1次。每次需要調(diào)整的高度為LogN,N為節(jié)點的個數(shù),因為節(jié)點個數(shù)每次少一個。
所以n-1次調(diào)整總次數(shù) = log2+log3+…+log(n-1)+log(n)≈log(n!)
由數(shù)學知識得log(n!)和nlog(n)是同階函數(shù)。
所以向下調(diào)整排序時間復雜度為N*LogN
所以堆排序時間復雜度為:N + N*LogN
大O漸進表示法為:O(N*LogN)
總結:堆排序時間復雜度 O(N*LogN)
二、向上調(diào)整堆排序
向上調(diào)整排序和向下調(diào)整排序的唯一不同在于建堆的不同,導致二者的建堆的時間復雜度略微不同。
1.向上調(diào)整建堆
向上調(diào)整建堆時間復雜度為N*LogN.具體原因還需要經(jīng)過殘酷的數(shù)學計算。孩子不會啊。但是經(jīng)過網(wǎng)上查閱資料我又找到了計算方法。如圖。
根據(jù)二叉樹的性質(zhì):h = Log2(N+1)
可以將T(h) = 2h * (h-2) + 2換為:
所以總體來說就是向上調(diào)整的建堆時間復雜度為O(N * LogN).
2.建堆代碼
思路:從第二個元素開始,只關注前兩個元素建堆,然后再依次增加元素建堆,使它一直為堆。
向上調(diào)整建堆雖然時間復雜度略高,但是代碼相對于向下調(diào)整簡單一點點。
void AdjustUp(int* a, int child) { //先把父親節(jié)點表示出來。 int parent = (child - 1) / 2; while (child > 0) { //比較孩子和父親,開始向上調(diào)整。 if (a[child] > a[parent]) { swap(&a[child], &a[parent]); child = parent; parent = (child - 1) / 2; } else { break; } } }
以上就是C語言植物大戰(zhàn)數(shù)據(jù)結構堆排序圖文示例的詳細內(nèi)容,更多關于C語言數(shù)據(jù)結構堆排序的資料請關注腳本之家其它相關文章!