原創公眾號：bigsai,碼字不易，如有幫助，記得三聯！

前言

在個人的專欄中，其他排序陸陸續續都已經寫了，而堆排序遲遲沒有寫，在國慶假期的尾聲，把堆排序也寫一寫。

插入類排序—(折半)插入排序、希爾排序
交換類排序—冒泡排序、快速排序手撕圖解
歸并類排序—歸并排序(逆序數問題)
計數排序引發的圍觀風波——一種O(n)的排序
兩分鐘搞懂桶排序

對于常見的快排、歸并這些O(nlogn)的排序算法，我想大部分人可能很容易搞懂，但是堆排序大部分人可能比較陌生，或許在Java的comparator接口中可能了解一點。但堆排序在應用中比如優先隊列此類維護動態數據效率比較高，有著非常廣泛的應用。

而堆排序可以拆分成堆和排序，其中你可能對堆比較陌生，對排序比較熟悉，下面就帶你徹底了解相關內容。

堆

什么是堆？

談起堆，很多人第一聯想到的是土堆，而在數據結構中這種土堆與完全二叉樹更像，而堆就是一類特殊的數據結構的統稱。堆通常是一個可以被看做一棵樹(完全)的數組對象。且總是滿足以下規則：

• 堆總是一棵完全二叉樹
• 每個節點總是大于(或小于)它的孩子節點。

完全二叉樹
我想什么是完全二叉樹大部分人也是知道：最后一層以上都是滿的，最后一層節點從左到右可以排列(有任何空缺即不滿足完全二叉樹)。

看作樹的數組對象
我們都知道我們排序的對象一般都是對數組之類的序列進行排序，如果轉成抽象數據結構再實現可能成本比較大。

我們正常在構造一棵二叉樹的時候通常采用鏈式left，right節點，但其實二叉樹的表示方式用數組也可以實現，只不過普通的二叉樹如果用數組儲存可能空間利用 效率會很低而很少采用，但我們的堆是一顆完全二叉樹。使用數組儲存空間使用效率也比較高，所以在形式上我們把這個數組看成對應的完全二叉樹，而操作上可以直接操作數組也比較方便。

大根堆 VS 小根堆
上面還有一點就是在這個完全二叉樹中所有節點均大于(或小于)它的孩子節點，所以這里就分為兩種情況

• 如果所有節點大于孩子節點值，那么這個堆叫做大根堆，堆的最大值在根節點。
• 如果所有節點小于孩子節點值，那么這個堆叫做小根堆，堆的最小值在根節點。

堆排序

通過上面的介紹，我想你對堆應該有了一定的認識，堆排序肯定是借助堆實現的某種排序，其實堆排序的整體思路也很簡單，就是

• 構建堆，取堆頂為最小(最大)。
• 將剩下的元素重新構建一個堆，取堆頂，一直到元素取完為止。

建堆

如果給一個無序的序列，首先要給它建成一個堆，我們如何實現這個操作呢？以下拿一個小根堆為例進行分析。

對于二叉樹(數組表示)，我們從下往上進行調整，從第一個非葉子節點開始向前調整，對于調整的規則如下：

①對于小根堆，當前節點與左右孩子比較，如果均小于左右孩子節點，那么它本身就是一個小根堆，它不需要做任何改變，如果左右有孩子節點比它還小，那么就要和最小的那個進行替換。

②但是普通節點替換可能沒問題，對于某些和子節點替換有可能改變子樹成堆，所以需要繼續往下判斷交換(最差判斷到葉子節點)。

分析構造堆的這個過程，每個非葉子節點都需要判斷比較是否交換，這樣一層就是O(n)，而每個節點可能替換之后影響子節點成堆需要再往下判斷遍歷，你可能會認為它是一個O(nlogn),但其實你看看二叉樹性值，大部分都是在底部的，上面的只有很少個數，如果你用數學方法去求得最終的復雜度它還是一個O(n)級別，這里就不作詳細介紹了。

一個大根堆建立過程也是一樣的：

堆排序

上面的一個堆建造完畢之后，我們怎么去利用這個堆實現排序呢？答案也是很簡單的，我們知道堆有一個特性就是堆頂是最小(或最大)，而我們建造這個如果去除第一個元素，剩余左右孩子依然滿足堆的性質。

將最后一個元素放置堆頂，由于第一個元素的存在使得整個不滿足堆的性質。分析這個結構，和我們前面構造堆的過程中構造到第一個元素的操作相同：

• 判斷左右孩子，如果需要交換則交換，交換后再次考慮交換子節點是否需要交換。一直到不需要考慮。

這樣到最后，堆排序即可完成，最終得到的序列即為堆排序序列。

一個大根堆的排序過程如下：

具體實現

有了上述的思想之后，如何具體的實現這個堆排序的代碼呢？
從細致的流程來看，大概流程是如下的：

給定數組建堆(creatHeap)

• 從第一個非葉子節點開始判斷交換下移(shiftDown)，使得當前節點和子孩子能夠保持堆的性值
• 如果交換打破子孩子堆結構性質，那么就要重新下移(shiftDown)被交換的節點一直到停止。

堆構造完成，取第一個堆頂元素為最小(最大)，剩下左右孩子依然滿足堆的性值，但是缺個堆頂元素，如果給孩子調上來，可能會調動太多并且可能破壞堆結構。

• 所以索性把最后一個元素放到第一位。這樣只需要判斷交換下移(shiftDown）,不過需要注意此時整個堆的大小已經發生了變化，我們在邏輯上不會使用被拋棄的位置，所以在設計函數的時候需要附帶一個堆大小的參數。
• 重復以上操作，一直堆中所有元素都被取得停止。

而堆算法復雜度的分析上，之前建堆時間復雜度是O(n)。而每次刪除堆頂然后需要向下交換，每個個數最壞為logn個。這樣復雜度就為O(nlogn).總的時間復雜度為O(n)+O(nlogn)=O(nlogn).

具體實現的代碼如下：

import java.util.Arrays;public class 堆排序 {static void swap(int arr[],int m,int n){int team=arr[m];arr[m]=arr[n];arr[n]=team;}//下移交換 把當前節點有效變換成一個堆(小根)static void shiftDown(int arr[],int index,int len)//0 號位置不用{int leftchild=index*2+1;//左孩子int rightchild=index*2+2;//右孩子if(leftchild>=len)return;else if(rightchild<len&&arr[rightchild]<arr[index]&&arr[rightchild]<arr[leftchild])//右孩子在范圍內并且應該交換{swap(arr, index, rightchild);//交換節點值shiftDown(arr, rightchild, len);//可能會對孩子節點的堆有影響，向下重構}else if(arr[leftchild]<arr[index])//交換左孩子{swap(arr, index, leftchild);shiftDown(arr, leftchild, len);}}//將數組創建成堆static void creatHeap(int arr[]){for(int i=arr.length/2;i>=0;i--){shiftDown(arr, i,arr.length);}}static void heapSort(int arr[]){System.out.println("原始數組為 ："+Arrays.toString(arr));int val[]=new int[arr.length]; //臨時儲存結果//step1建堆creatHeap(arr);System.out.println("建堆后的序列為 ："+Arrays.toString(arr));//step2 進行n次取值建堆，每次取堆頂元素放到val數組中，最終結果即為一個遞增排序的序列for(int i=0;i<arr.length;i++){val[i]=arr[0];//將堆頂放入結果中arr[0]=arr[arr.length-1-i];//刪除堆頂元素，將末尾元素放到堆頂shiftDown(arr, 0, arr.length-i);//將這個堆調整為合法的小根堆，注意(邏輯上的)長度有變化}//數值克隆復制for(int i=0;i<arr.length;i++){arr[i]=val[i];}System.out.println("堆排序后的序列為:"+Arrays.toString(arr));}public static void main(String[] args) {int arr[]= {14,12,16,8,9,1,14,9,6 };heapSort(arr); }}

執行結果：

當然，代碼為了成章節我把它命名為中文，還有些不規范的地方請注意甄別。

對于堆排序就先介紹到這里了，當然堆的強大之處不止這么一點，優先隊列同樣也是用到堆但是這里就不詳細介紹了，我相信優秀的你肯定又掌握了一門O(nlogn)級別的排序算法啦。如果寫的有啥不確切地方還請指正。

結語

原創不易，最后我請你幫兩件事幫忙一下:

star支持一下， 您的肯定是我在csdn平臺創作的源源動力。

微信搜索「bigsai」，關注我的公眾號，不僅免費送你電子書，我還會第一時間在公眾號分享知識技術。加我還可拉你進力扣打卡群一起打卡LeetCode。

記得關注、咱們下次再見！

總結

以上是生活随笔為你收集整理的【排序算法】— 手写堆排序的全部內容，希望文章能夠幫你解決所遇到的問題。

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