簡介：

??之前對堆排序認識的不是很透徹，今天回過頭來再把堆排序的知識整理整理！以及排升序為什么要建大堆，排降序要建小堆。

正文：

??首先我們要知道：
??①堆的邏輯是一顆完全二叉樹；
??②它使用的是順序存儲(也就是數組)；
??③它的作用：一般都是用于找最值。

排序也就是對數組的元素按照大小規則進行擺放。

堆排序的過程：
1、建堆
2、對建好的堆進行向下調整。

可能有人會疑問？堆已經建立好了，為什么還要向下調整？
來看看下面的解釋：
我們先給定一個數組arr[ ] = { 7, 6, 3, 5, 4, 1, 2 }; 將其排成一個大堆。如下圖：

??當我們建好堆之后，我們發現這個堆層序遍歷下來是一個降序的。那么要將它變成一個升序的順序，就要將它逆序。
??也就是交換堆頂和最后一個元素的位置，然后從堆頂開始向下調整，每交換一個位置，就多一個數據已經排好升序。
??可能看到這還很迷糊。沒關系，繼續看下面的圖。

我們可以看到，排升序的話，使用大堆是非常方便的，我們每次向下調整都可以得到剩余數據的最大值，即堆頂元素。然后放到最后，使用分治的思想，每調整一次，要排序的數據就少一個。當交換到最后一個結點時，數組已經排好序了。
因為是從堆頂選擇第一個元素與最后一個元素交換，所以堆排序實質上還是選擇排序。

那么有人會疑惑為什么不使用小堆排升序呢？
我們再想想：首先使用堆排序主要是用堆頂元素，如果使用小堆排升序，此時堆頂的元素是最小的，當我們取出堆頂元素時，此時小根堆的性質就變了，那么下次就找不到第二小的元素了，還要重新建堆。所以不能使用小堆排升序。有興趣的可以自己來畫圖走一走。

---

堆排序的代碼如下：

void Swap(int *a, int *b) {int tmp = *a;*a = *b;*b = tmp; } //建大堆 void AdjustDown(int arr[], int size, int root){int left = 2 * root + 1;int right = 2 * root + 2;int max;//沒有左孩子if (left >= size){return;}//右孩子存在且大于左孩子if (right < size && arr[right] > arr[left]){max = right;}else{max = left;}if (arr[root] >= arr[max]){return;}Swap(arr + root, arr + max);AdjustDown(arr, size, max); } void CreateHeap(int arr[], int size){for (int i = (size - 1 - 1) / 2; i >= 0; i--){AdjustDown(arr, size, i);} } void HeapSort(int arr[], int size){CreateHeap(arr, size);for (int i = 0; i < size; i++){Swap(arr, arr + size - i - 1);AdjustDown(arr, size - i - 1, 0);} }

總結

以上是生活随笔為你收集整理的堆排序(排升序为啥建大堆，排降序为啥建小堆)的全部內容，希望文章能夠幫你解決所遇到的問題。

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