我們在介紹《什么是優(yōu)先隊列》的時候就注意到翔横，如果每次都刪除堆頂元素，那么將會得到一個有序的數(shù)據(jù)效览。因此荡短，我們可以利用二叉堆來對數(shù)據(jù)進行排序。?點我查看本文代碼地址瘦锹。
堆排序分析
通過前面的學習我們可以看到沼本，如果構(gòu)建一個二叉堆锭沟，最后每次從堆頂取出一個元素，那么最終取出元素就是有序的辫红，不過如果要用來對數(shù)據(jù)按照從小到大排序，就不是構(gòu)造小頂堆切油，而是大頂堆了名惩，即堆頂元素大于等于其左右兒子節(jié)點娩鹉。總結(jié)堆排序思路如下：
以O(shè)(N)時間復雜度構(gòu)建N個元素的二叉堆
以O(shè)(logN)時間復雜度刪除一個堆頂元素戚宦，N個元素時間復雜度為O（NlogN）
由于刪除一個堆頂元素時锈嫩，就會空出一個位置呼寸，為了節(jié)省空間，將刪除的堆頂元素放到數(shù)組末尾
當堆為空時对雪，完成排序
由于數(shù)組元素從下標0開始慌植，因此每個位置必須利用好。假設(shè)堆頂元素位置為i,那么左右兒子節(jié)點位置分別為2i+1,2i+2
實例分析
根據(jù)前面的分析丈钙，我們來看一個具體的例子交汤。假設(shè)我們要對
進行排序芙扎。
該數(shù)據(jù)構(gòu)成的原始二叉樹如下：
構(gòu)建二叉堆
為了能夠使得數(shù)組所有元素滿足堆的性質(zhì)戒洼，即父節(jié)點大于等于兒子節(jié)點，我們需要從倒數(shù)第二層開始調(diào)整（為什么不是從最后一層寥掐？）。即調(diào)整8和10百炬。
對于8來說污它，找到它的兒子節(jié)點中較大的一個衫贬，即35,將8和35交換后如下：
此時數(shù)組數(shù)據(jù)為：
對于10來說，它比左右兒子節(jié)點都大，因此不需要調(diào)整缝呕。
對于１來說斧散，它的右兒子35最大鸡捐，因此需要調(diào)整，和右兒子交換后如下：
此時數(shù)組數(shù)據(jù)為：
但是一次交換后源祈，我們發(fā)現(xiàn)香缺，１的左兒子還是比它大歇僧，因此交換它和較大的左兒子的位置，交換后如下：
此時數(shù)組數(shù)據(jù)為：
最終我們得到了滿足堆性質(zhì)的二叉堆了。
基于二叉堆的排序
在堆創(chuàng)建好后侥钳，每次取出堆頂元素舷夺，并且調(diào)整堆鄙陡，把堆頂元素放在數(shù)組最后即可躏啰。
例如给僵，對于前面創(chuàng)建好的堆，堆頂元素是35蔓同，我們?nèi)〕龅趇（此時為1）個元素35蹲诀，并把堆最后一個元素放在數(shù)組倒數(shù)第i個位置：
為了滿足堆性質(zhì)脯爪，我們需要調(diào)整堆頂元素痕慢，因為堆頂元素目前不滿足堆性質(zhì)，因此需要交換8和15的位置：
此時所有元素再次滿足堆性質(zhì)快骗。
此時數(shù)組數(shù)據(jù)為：
對于其他元素也是同樣的操作方篮，因此不再贅述励负。
代碼實現(xiàn)
根據(jù)上面的分析熄守，關(guān)鍵代碼實現(xiàn)如下：
voidadjust_ele(ElementType arr[],inti,intlength){intchild ;? ? ElementType temp;for(temp = arr[i];2*i+1< length;i = child)? ? {? ? ? ? child =2* i +1;/*找到較大的兒子*/if(child != length-1&& arr[child+1] > arr[child])? ? ? ? ? ? child+=1;/*如果空穴元素小于該兒子，則空穴下滑*/if(temp < arr[child])? ? ? ? ? arr[i] = arr[child];elsebreak;? ? }/*將i位置的元素放到正確的位置*/arr[i] = temp;}voidheap_sort(ElementType arr[],intlength){inti =0;/*構(gòu)建堆*/for(i = length /2;i >=0;i--)? ? {? ? ? ? adjust_ele(arr,i,length);//printArr(arr,length);}for(i = length-1;i >0;i--)? ? {/*填充i位置的空穴*/swap(&arr[0],&arr[i]);/*每次都處理堆頂元素*/adjust_ele(arr,0,i);//printArr(arr,length);}}
完整可運行代碼地址：?heapSort
運行結(jié)果：
beforesort:1108571535aftersort:1578101535
總結(jié)
結(jié)合我們前面介紹的優(yōu)先隊列攒发，我們很容易理解堆排序晋南，不過需要注意的就是位置0必須使用上负间。另外通過利用刪除堆頂元素后空出來的位置姜凄，避免了另外申請數(shù)組內(nèi)存來存放排序好的數(shù)組趾访。建議自己修改完整可運行代碼扼鞋，來觀察數(shù)據(jù)調(diào)整情況。
看我主頁簡介免費C++學習資源捐友，視頻教程溃槐、職業(yè)規(guī)劃昏滴、面試詳解猴鲫、學習路線、開發(fā)工具
每晚8點直播講解C++編程技術(shù)影涉。
