上一章節已經詳細的向大家介紹過排序的相關概念（學習筆記-排序簡單介紹） ，本文旨在為大家詳細的介紹堆排序。

堆排序（英語：Heapsort）是指利用堆這種數據結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子結點的鍵值或索引總是小于（或者大于）它的父節點。

堆(Heap)是計算機科學中一類特殊的數據結構的統稱。堆是一種非線性結構。可以把堆看作一個數組，也可以被看作一個完全二叉樹，通俗來講堆其實就是利用完全二叉樹的結構來維護的一維數組。此處用到的堆一般是指大頂堆或小頂堆。

大頂堆

每個結點的值都大于或等于其左右孩子結點的值，稱為大頂堆。如下圖所示。

小頂堆

每個結點的值都小于或等于其左右孩子結點的值，稱為小頂堆。如下圖所示。

将待排序序列構造成一個大頂堆，此時，整個序列的最大值就是堆頂的根節點。将其與末尾元素進行交換，此時末尾就為最大值。然後将剩餘n-1個元素重新構造成一個堆，這樣會得到n個元素的次小值，如此反複執行，便能得到一個有序序列了。需要注意的是建立大頂堆時是從最後一個非葉子節點開始從下往上調整的。

1. 創建一個堆 R[0……n-1]；

2. 把堆首（最大值）和堆尾互換；

3. 把堆的尺寸縮小 1（已經有序的部分不進入下一輪）；

4. 重複步驟 2，直到堆的尺寸為 1。

操作過程如下：

1，初始化堆：将R[1..n]構造為堆；

2，将當前無序區的堆頂元素R[1]同該區間的最後一個記錄交換，然後将新的無序區調整為新的堆。

#include <stdio.h> #define elemType int /*元素類型*/ int k=1;//輪次記錄 //打印函數 void Print (elemType arr[], int len){ int i; for (i=0; i<len; i ){ printf ("%d\t", arr[i]); } printf("\n"); } //記錄交換 void swap(int* a, int* b) { int temp = *b; *b = *a; *a = temp; } //構建大頂堆 void max_heapify(int a[], int start, int end) { //建立父節點指标和子節點指标 int dad = start; int son = dad * 2 1; //若子節點指标在範圍内才做比較 while (son <= end){ if (son 1 <= end && a[son] < a[son 1]) { //先比較兩個子節點大小，選擇最大的 son ; } //如果父節點大於子節點代表調整完畢，直接跳出函數 if (a[dad] > a[son]){ return; }else{ //否則交換父子内容再繼續子節點和孫節點比較 swap(&a[dad], &a[son]); dad = son; son = dad * 2 1; } } } //排序 void Sort(elemType a[], int len) { int i; //初始化，i從最後一個父節點開始調整 for (i = len / 2 - 1; i >= 0; i--){ max_heapify(a, i, len - 1); } for (i = len - 1; i > 0; i--) { //先将第一個元素和已排好元素前一位做交換，再重新調整，直到排序完畢 swap(&a[0], &a[i]); max_heapify(a, 0, i - 1); printf("第===%d===輪排序後結果如下：\n",k); Print (a, 9); k=k 1; } } int main() { int i; elemType arr[9] = {94,19,29,9,11,1,14,13,29}; printf("待排序的序列為：\n"); Print(arr, 9); printf("\n\n"); Sort (arr,9); printf("\n\n"); printf("排好序的結果如下：\n"); Print(arr, 9); }

時間複雜度

堆排序的運行時間主要是消耗在構建堆和在重建堆時的反複篩選上。在構建堆的過程，因為我們是從完全二叉樹最下層的非葉子結點開始構建的，将它與其孩子結點進行比較和有必要的互換，對于每個非葉子結點來說，其實最多2次比較和互換，故初始化堆的時間複雜度為O(n)。在正式排序的時候，第i次取堆頂記錄和重建堆需要O(logi)的時間（完全二叉樹的某個結點到根結點的距離為log2i 1）,并且需要取n-1次堆頂記錄，因此重建堆的時間複雜度為O(nlogn)。所以總的來說，堆排序的時間複雜度為O(nlogn)。由于堆排序對元素記錄的排序狀态不敏感，因此它無論最好，最壞，和平均時間複雜度均為O(nlogn)。

空間複雜度

堆排序中隻有交換元素時需要1個輔助空間，與問題規模無關，空間複雜度為O(1)。

排序穩定性

在構建堆的過程中無法保證相同值構建前後的相對位置，所以堆排序是不穩定的。

本文的初衷為學習筆記的分享，部分圖文來源于網絡，如侵，聯删。

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!