基本概念：堆排序是一種特殊的樹形數據結構，其每個節點都有一個值，通常提到的堆都是指一棵完全二叉樹，

根節點的值小于(或大于)兩個子節點的值，同時根節點的兩個子樹也分別是一個堆。堆排序主要包括兩個過程：

一是構建堆， 二是交換堆頂元素與最后一個元素的位置。

?

堆排序思想:
1.?? 將序列構造成一棵完全二叉樹 ；
2.?? 把這棵普通的完全二叉樹改造成堆，便可獲取最小值 ；
3.?? 輸出最小值 ；
4.?? 刪除根結點，繼續改造剩余樹成堆，便可獲取次小值 ；
5.?? 輸出次小值 ；
6.?? 重復改造，輸出次次小值、次次次小值，直至所有結點均輸出，便得到一個排序 。

?

堆排序的特點：

穩? 定? 性：不穩定

時間復雜度：O(nlogn)

堆排序對記錄較少的文件效果一般，但對于記錄較多的文件很有效果，其運行時間主要耗費在創建堆與調整堆上。

?

1 #include <iostream> 2 3 using namespace std; 4 5 void AdjustMinHeap(int *a, int pos, int len) 6 { 7 int temp; 8 int child; 9 10 for (temp = a[pos]; 2 * pos + 1 <= len; pos = child) 11 { 12 child = 2 * pos + 1; 13 if (child < len && a[child] > a[child + 1]) 14 { 15 child++; 16 } 17 if (a[child] < temp) 18 { 19 a[pos] < a[child]; 20 } 21 else 22 { 23 break; 24 } 25 } 26 a[pos] = temp; 27 } 28 29 void Swap(int a, int b) 30 { 31 int temp; 32 temp = a; 33 a = b; 34 b = temp; 35 } 36 37 void PrintArray(int *a, int length) 38 { 39 int i; 40 41 for (i = 0; i < length; i++) 42 { 43 printf("%d ", a[i]); 44 } 45 printf("\n"); 46 } 47 48 void HeapSort(int *array, int len) 49 { 50 int i; 51 52 for (i = len / 2 - 1; i >= 0; i--) 53 { 54 AdjustMinHeap(array, i, len - 1); 55 } 56 for (i = len -1; i >= 0; i--) 57 { 58 Swap(array[0], array[i]); 59 AdjustMinHeap(array, 0, i - 1); 60 } 61 } 62 63 int main() 64 { 65 int array[] = {0, 13, 1, 14, 27, 18}; 66 int length = sizeof(array) / sizeof(array[0]); 67 68 HeapSort(array, length); 69 PrintArray(array, length); 70 while(1); 71 return 0; 72 }

?

轉載于:https://www.cnblogs.com/kutoli/p/8337907.html

總結

以上是生活随笔為你收集整理的八种排序整理（六）----堆排序的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。