欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C語言八大排序之堆排序

 更新時間：2022年02月24日 16:54:12   作者：檸檬葉子C  
堆排序是利用堆這種數(shù)據(jù)結構而設計的一種排序算法，堆排序是一種選擇排序，它的最壞，最好，平均時間復雜度均為O(nlogn)，它也是不穩(wěn)定排序

前言

本章我們來講解八大排序之堆排序。2022，地球Online新賽季開始了！讓我們一起努力內卷吧！

一、堆排序的概念

?? 堆排序（Heapsort）：利用堆積樹（堆）這種數(shù)據(jù)結構所設計的一種排序算法，它是選擇排序的一種。通過堆來進行選擇數(shù)據(jù)，需要注意的是 排升序要建大堆，排降序建小堆。

堆排序使用堆來選數(shù)，效率就高了很多。

  • 時間復雜度：{\color{Red} O}({\color{Blue} N}*log{\color{Blue} N})
  • 空間復雜度：{\color{Red} O}(1)
  • 穩(wěn)定性：不穩(wěn)定

二、堆排序的實現(xiàn)

我們先創(chuàng)建一個堆排序的函數(shù)：

void HeapSort(int arr[], int n);

假設我們要對下列數(shù)組來使用堆排序（升序）：

int arr[] = {70, 56, 30, 25, 15, 10, 75};

根據(jù)我們之前學到的知識，數(shù)組是可以直接看作為完全二叉樹的，所以我們可以把它化為堆。此時我們就可以 "選數(shù)" （堆排序本質上是一種選擇排序）。

第一步：構建堆

第一步就是要想辦法把 arr 數(shù)組構建成堆（這里我們先構建成小堆）。我們介紹兩種方法，分別為向上調整算法和向下調整算法：

方法1：向上調整

通過我們之前學過的 "向上調整" ，利用插入的思路來解決。首先設計下向上調整的算法：

void Swap(HPDataType* px, HPDataType* py) {
    HPDataType tmp = *px;
    *px = *py;
    *py = tmp;
}
/* 小堆的向上調整 */
void AdjustUp(int* arr, int child) {
    assert(arr);
    // 首先根據(jù)公式計算算出父親的下標
    int parent = (child - 1) / 2;
    // 最壞情況:調到根，child=parent 當child為根節(jié)點時結束（根節(jié)點永遠是0）
    while(child > 0) {
        if(arr[child] < arr[parent]) {  // 如果孩子小于父親（不符合小堆的性質）
            // 交換他們的值
            Swap(&arr[child],&arr[parent]); // 傳地址
            // 往上走
            child = parent;
            parent = (child - 1) / 2;
        } else {  // 如果孩子大于父親（符合小堆的性質）
            // 跳出循環(huán)
            break;  
        }
    }
}

① 首先，通過公式計算出父親的下標，公式如下：

② 其次，設計循環(huán)部分，最壞情況為調到根，如果已經符合大堆的條件則終止循環(huán)。

③ 進入循環(huán)后進行判斷，如果 child ＞ parent，則交換它們的值，讓父親獲得孩子的值，孩子得到父親的值，從而讓它們符合大堆的性質。

④ 交換完畢后，以便于繼續(xù)判斷，我們需要更新 child 和 parent 指向的元素，做到 "往上走"

此時，我們把數(shù)組里的元素依次調整即可。

?? 方法1：

/* 升序 */
void HeapSort(int arr[], int n) {
    for (int i = 1; i < n; i++) {
        AdjustUp(arr, i);   // 傳入數(shù)組 和 child的下標
    }
}

我們不需要從 0 開始調，從 1 開始調。所以 i 的起始值設置為 1 。此時，小堆就構建好了。

方法2：向下調整

向下調整算法我們在堆那個章節(jié)也學過了，這里我們再來復習一下：

void SmallAjustDown(int* arr, int n, int parent) {
    int child = parent * 2 + 1; // 默認為左孩子
    while(child < n) { // 葉子內
        // 選出左右孩子中小的那一個
        if(child + 1 < n && arr[child + 1] < arr[child]) {
            child = child + 1;
        }
        // 如果孩子小于父親（不符合小堆的性質）
        if(arr[child] < arr[parent]) {  
            // 交換它們的值
            Swap(&arr[child], &arr[parent]);
            // 往下走
            parent = child;
            child = parent * 2 + 1;
        } else { // 如果孩子大于父親（符合小堆的性質）
            // 跳出循環(huán)
            break;
        }
    }
}

① 因為要考慮左孩子還是右孩子，我們可以定義兩個變量，分別記錄左孩子和有孩子。但是我們這里可以用更好的方法，只需要定義一個孩子即可。具體實現(xiàn)方法如下：首先創(chuàng)建 child，我們先默認它是左孩子，利用傳進來的 parent 根據(jù)公式計算出 child 的大?。?/p>

因為我們暫且默認為左孩子，我們隨后進入循環(huán)后要進行檢查，看看是左孩子大還是右孩子大，這里我們只需要根據(jù)數(shù)組的性質，將 child + 1 即可得到右孩子的下標，從而方便我們進行比較。比較完畢后將 child 重新賦值，拿個孩子小就將 child 給誰。

② 一共有兩個結束條件（出口），第一個結束條件是父親小于孩子就停止，第二個結束條件是chi調整到葉子。所以，循環(huán)體判斷部分根據(jù)我們分析的結束條件，如果調整到葉子就結束，我們接受了 n，也就是數(shù)組的大小，只要 child 超過數(shù)組的大?。╟hild > n） 就結束，這是第一個出口。

③ 進入循環(huán)后，對比左孩子和右孩子哪一個更小，child 就交付給誰。這里還要注意的是，要防止孩子不存在的情況，如果 child + 1 比 n 大，就說明孩子不存在。所以我們再寫 if 判斷條件的時候就要注意了，我們加一個 child + 1 < n 的條件限制一下：

 if(child + 1 < n && arr[child + 1] < arr[child]) {...}

④ 確認好較小的孩子后，我們就可以開始比較孩子和父親的大小了。如果孩子小于父親，就不符合小堆的性質，我們就要交換它們的值。這里我們直接調用我們剛才寫的 Swap 接口即可，這就是為什么在寫向上調整的時候要我們單獨把交換部分的代碼寫成函數(shù)的原因。

⑤ 交換完畢后，他們的值已經互相交換好了，這時我們要改變 parent 和 child 的指向，讓它們往下走，parent = child ，child 再次根據(jù)公式算出新的 child 即可。

⑥ 設計下 if 的 else 部分，如果數(shù)組的 child 的值大于 parent 的值，說明符合小堆的性質了， break 跳出循環(huán)即可，這是第二個出口。

向下調整算法的前提：左右子樹必須都是小堆

如果左子樹和右子樹不是小堆，怎么辦？

可以用遞歸解決，但是我們能用循環(huán)就用循環(huán)來解決：

葉子所在的子樹是不需要調的。所以，我們從倒著走的第一個非葉子結點的子樹開始調。

 （所以我們先調整30）

為了能夠演示得更明顯，我們再給數(shù)組再加點數(shù)據(jù)，假設我們需要對以下數(shù)組排序：

這里，我們找到了15。

…… 下標不斷地 - - 后：

由于，從倒著走的第一個非葉子結點的子樹開始調，即，最后一個節(jié)點的父親。

我們已知最后一個節(jié)點的下標為：  n-1

那么，我們可以通過公式計算出他父親的下標： parent = \frac{child -1}{2} \rightarrow \frac{\, \, \, [\, \, (n-1)-1\, \, ]\, \, \, }{2}

?? 方法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é)點的父親
	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;
}
 
/* 小堆下調 */
void AdjustDown(int arr[], int sz, int father_idx) {
    int child_idx = father_idx * 2 + 1;                                        // 計算出左孩子的值（默認認為左孩子大）
    while (child_idx < sz) {                                                   // 最壞情況：調到葉子（child >= 數(shù)組范圍時必然已經調到葉子）
        if ((child_idx + 1 < sz) && (arr[child_idx + 1] < arr[child_idx])) {   // 如果右孩子存在且右孩子比左孩子小
            child_idx = child_idx + 1;                                         // 讓其代表右孩子
        }
        if (arr[child_idx] < arr[father_idx]) {                                // 如果孩子的值小于父親的值（大符合小堆的性質）
            Swap(&arr[child_idx], &arr[father_idx]);                           // 交換它們的值
            /* 往下走 */
            father_idx = child_idx;                                            // 更新下標
            child_idx = father_idx * 2 + 1;                                    // 計算出該節(jié)點路線的新父親
        } else {                                                               // 如果孩子的值大于父親的值（符合小堆的性質）
            break;                                                             // 終止循環(huán)
        }
    }
}
 
/* 升序 */
void HeapSort(int arr[], int sz) {
	/* 創(chuàng)建大堆，選出最大的數(shù)  O(N)  */
	int father = ((sz - 1) - 1) / 2;  // 計算出最后一個葉子節(jié)點的父親
	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; 
}

?? 運行結果：10 15 30 25 56 70 75 33 50 69

第二步：排序

剛才介紹了兩種方法來構建堆，現(xiàn)在堆已經構建完畢了，我們可以開始設計排序部分的算法了。

? 如果排升序，建小堆……

① 選出最小的數(shù)，放到第一個位置，這很簡單，直接取頂部就可以得到最小的數(shù)。

② 但問題來了，如何選出次小的數(shù)呢？

從 15 開始，剩下的元素看作一個堆。但是這之前建立好的堆關系全部亂了！你還得重新建堆，才能選出次小的數(shù)。建堆的時間復雜度為 {\color{Red} O}({\color{Blue} N})，需要不斷地建堆 N \, \, N-1 \, \, N-2 \, \, N-4 ...則用小堆的時間復雜度就是 {\color{Red} O}({\color{Blue} N }*{\color{Blue} N})，這太離譜了！搞了一大圈結果居然是N*N，還不如直接遍歷選出來的方便呢。

建小堆來排升序是完全可以的，但是效率太低！完全沒有體現(xiàn)出你用堆的優(yōu)勢！

? 解決方法：使用大堆來排升序！

?? 我們剛才已經實現(xiàn)好小堆了，根據(jù)上一節(jié)學到的知識，小堆要變成大堆，直接把剛才的代碼的 "<" 改成 ">" 即可： 

#include <stdio.h>
 
/* 交換函數(shù) */
void Swap(int* px, int* py) {
    int tmp = *px;
    *px = *py;
    *py = tmp;
}
 
/* 大堆下調 */
void AdjustDown(int arr[], int sz, int father_idx) {
    int child_idx = father_idx * 2 + 1;                                        // 計算出左孩子的值（默認認為左孩子大）
    while (child_idx < sz) {                                                   // 最壞情況：調到葉子（child >= 數(shù)組范圍時必然已經調到葉子）
        if ((child_idx + 1 < sz) && (arr[child_idx + 1] > arr[child_idx])) {   // 如果右孩子存在且右孩子比左孩子大
            child_idx = child_idx + 1;                                         // 讓其代表右孩子
        }
        if (arr[child_idx] > arr[father_idx]) {                                // 如果孩子的值大于父親的值（不符合大堆的性質）
            Swap(&arr[child_idx], &arr[father_idx]);                           // 交換它們的值
            /* 往下走 */
            father_idx = child_idx;                                            // 更新下標
            child_idx = father_idx * 2 + 1;                                    // 計算出該節(jié)點路線的新父親
        } else {                                                               // 如果孩子的值小于父親的值（符合大堆的性質）
            break;                                                             // 終止循環(huán)
        }
    }
}
 
/* 升序 */
void HeapSort(int arr[], int sz) {
	/* 創(chuàng)建大堆，選出最大的數(shù)  O(N)  */
	int father = ((sz - 1) - 1) / 2;  // 計算出最后一個葉子節(jié)點的父親
	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; 
}

?? 運行結果：75 69 70 50 56 10 30 33 25 15

?? 現(xiàn)在改成了大堆，我們要排升序，我們可以讓堆頂數(shù)和最后的數(shù)進行交換：

這并不會帶來堆結構的破壞！我們把75不看作堆的一部分即可。再進行向下調整，就可以找到次小的數(shù)了。此時時間復雜度為 

{\color{Red} O}({\color{Blue} N} * log{\color{Blue} N})

?? 步驟總結：

① 建大堆，選出最大的數(shù)。

② 最大的數(shù)跟最后一個數(shù)交換。

③ 如何選出次大的數(shù)呢？把最后一個數(shù)不看作堆里面，進行向下調整。

?? 代碼實現(xiàn)（用 while）：

/* 堆排序 - 升序 */
void HeapSort(int arr[], int sz) {
	/* 創(chuàng)建大堆，選出最大的數(shù)  O(N)  */
	int father = ((sz - 1) - 1) / 2;  // 計算出最后一個葉子節(jié)點的父親
	while (father >= 0) {
		AdjustDown(arr, sz, father);
		father--;
	}
 
	/* 依次選數(shù)，調堆   O(N * logN)  */
	int end = sz - 1;
	while (end > 0) {
		Swap(&arr[0], &arr[end]);      // 最大的數(shù)跟最后一個數(shù)交換
		AdjustDown(arr, end, 0);       // 調堆，選出次大的數(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);    // 調堆，選出次大的數(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é)點的父親
	while (father >= 0) {
		AdjustDown(arr, sz, father);
		father--;
	}
 
	/* 依次選數(shù)，調堆   O(N * logN)  */
	int end = sz - 1;
	while (end > 0) {
		Swap(&arr[0], &arr[end]);      // 最大的數(shù)跟最后一個數(shù)交換
		AdjustDown(arr, end, 0);       // 調堆，選出次大的數(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;
}

?? 運行結果：

? 如果要排降序呢？使用小堆即可！

?? 降序：使用小堆 

#include <stdio.h>
 
/* 交換函數(shù) */
void Swap(int* px, int* py) {
    int tmp = *px;
    *px = *py;
    *py = tmp;
}
 
/* 小堆下調 */
void AdjustDown(int arr[], int sz, int father_idx) {
    int child_idx = father_idx * 2 + 1;                                        // 計算出左孩子的值（默認認為左孩子大）
    while (child_idx < sz) {                                                   // 最壞情況：調到葉子（child >= 數(shù)組范圍時必然已經調到葉子）
        if ((child_idx + 1 < sz) && (arr[child_idx + 1] < arr[child_idx])) {   // 如果右孩子存在且右孩子比左孩子小
            child_idx = child_idx + 1;                                         // 讓其代表右孩子
        }
        if (arr[child_idx] < arr[father_idx]) {                                // 如果孩子的值小于父親的值（不符合小堆的性質）
            Swap(&arr[child_idx], &arr[father_idx]);                           // 交換它們的值
            /* 往下走 */
            father_idx = child_idx;                                            // 更新下標
            child_idx = father_idx * 2 + 1;                                    // 計算出該節(jié)點路線的新父親
        }
        else {                                                               // 如果孩子的值大于父親的值（符合小堆的性質）
            break;                                                             // 終止循環(huán)
        }
    }
}
 
/* 堆排序 - 降序 */
void HeapSort(int arr[], int sz) {
	/* 創(chuàng)建大堆，選出最大的數(shù)  O(N)  */
	int father = ((sz - 1) - 1) / 2;  // 計算出最后一個葉子節(jié)點的父親
	while (father >= 0) {
		AdjustDown(arr, sz, father);
		father--;
	}
 
	/* 依次選數(shù)，調堆   O(N * logN)  */
	int end = sz - 1;
	while (end > 0) {
		Swap(&arr[0], &arr[end]);      // 最大的數(shù)跟最后一個數(shù)交換
		AdjustDown(arr, end, 0);   // 調堆，選出次小的數(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;
}

?? 運行結果：

四、證明建堆的時間復雜度

因為堆是完全二叉樹，而滿二叉樹也是完全二叉樹。此處為了簡化，將采用滿二叉樹來證明。（時間復雜度本來看的就是近似值，所以多幾個節(jié)點不會影響最終結果）：

假設樹的高度為h：

第 1層：2^0個節(jié)點，需要向下移動h-1層

第2層：2^1個節(jié)點，需要向下移動h-2層

第 3層：2^2個節(jié)點，需要向下移動h-3層

第4層：2^3個節(jié)點，需要向下移動h-4 層

……

第 h - 1 層：2^{h-2} 個節(jié)點，需要向下移動1 層

則需要移動節(jié)點總的移動步數(shù)為：

T(n) = 2^0 * (h-1) + 2^1 *(h-2) + 2^2 * (h-3) + 2^3 * (h-4) + ... + 2^{h-3} * 2 + 2^{h-2} * 1

   ①

2T(n) = 2^1*(h-1)+2^2*(h-2)+2^3*(h-3)+2^4*(h-4)+...+2^{h-2}*2+2^{h-1}*1

   ②

② - ① 錯位相減：

T(n) = 1-h+2^1+2^2+2^3+2^4+...+2^{h-2}+2^{h-1}

T(n) = 2^0+2^1+2^2+2^3+2^4+...+2^{h-2} + 2^{h-1}-h

T(n) = 2^h - 1 - h

n = 2^h-1\, \, \, \, \,\, \, \, \, \, \, h = log_2(n+1)

T(n) = n-log_2(n+1) \approx n

因此，建堆的時間復雜度為 {\color{Red} O}({\color{Blue} N})  

參考資料：

Microsoft. MSDN(Microsoft Developer Network)[EB/OL]. []. .

百度百科[EB/OL]. []. https://baike.baidu.com/.

?? 筆者：王亦優(yōu)

?? 更新： 2021.11.26

? 勘誤： 無

?? 聲明： 由于作者水平有限，本文有錯誤和不準確之處在所難免，本人也很想知道這些錯誤，懇望讀者批評指正！

本篇完。

到此這篇關于C語言八大排序之堆排序的文章就介紹到這了,更多相關C語言 堆排序內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！

相關文章

最新評論