1、堆排序效能簡介
堆排序也是一種應用分治演算法（建堆時應用了該思想）的排序方法，時間復雜度為無論在最好還是最壞情況下都為O[ n log(n）],相比于穩定的歸并排序或是速度更勝一籌的快速排序（最好情況下O（n）），需要頻繁進行交換以換取O（1）空間復雜度優勢的堆排序，在如今大記憶體的硬體支持下似乎并沒有如此的必要了，但是堆排序還是有它更特化的應用場景的，比如在大量資料中獲取前Top幾的記錄，在這種情形下，堆排序實際比快排更高效，
2、什么是堆？它在序列中的表現形式如何？
想了解好堆排序，那首先得知道什么是堆，當然很多基礎扎實的小伙伴肯定都知道，堆就是一個有著父節點大于（或小于）其子節點性質的完全二叉樹（大于的是大頂堆，小于則是小頂堆），
如果我們以一個序列（陣列）來表現堆的話，按從堆頂先左右后上下的順序標記下標的話，那就會有如下規律：
①下標為 i 的節點，其左孩子節點下標為 2i+1 ,右孩子下標為 2i+2 ，
②非葉子節點的下標為 0 至 array.length/2 - 1 ，
③如果一個節點只有一個葉子，那么它必然是左葉子，即一個節點的左葉子為空，那么這個節點必然是葉子節點，（實際上，只有最后一個非葉子節點才可能會有單葉子，即序列中下標為array.length/2 - 1的非葉子節點）
3、堆排序的流程
有一些小伙伴覺得堆排序有點復雜，看了動態演示圖也覺得有點難，其實我個人觀點覺得堆排序的更適合從邏輯角度理解，看堆排序的動態演示圖反而更容易使人迷惑，
實際上，堆排序一共就做兩大步：
第一步，建立堆，或者說將序列（陣列）堆化，即2中我提到的，將堆在序列中表現出來，
在代碼的實作中，我們建立堆的程序實際上就是應用了分治的思想，我們從最后一個非葉子節點開始堆化，然后逐漸向前對其他非葉子節點進行堆化，當我們堆化到子樹更大的非葉子節點時，我們會發現，這些子樹已經作為先前的小問題被我們堆化過，只要當前的非葉子節點在堆化時不用與孩子節點交換，我們就無需再對子樹進行二次堆化，如下圖：
（再次注意，子樹堆化過不代表它不會再變了，當需要堆化的節點要與其已經堆化的孩子節點交換時，我們還要在交換后對孩子節點再次堆化）
很多小伙伴看不懂堆排代碼的第一個坎兒就在于沒理解建堆時對分治思想的應用，
第二步，逐個把堆頂的元素（即最大值或最小值）拿出來扔到有序區，然后維護堆，
這里，我們邏輯上取出堆頂的元素放入有序區的流程在代碼中其實只要用一個交換就可以實作，即堆頂元素與當前的堆尾元素交換，因為堆頂取走一個元素會使堆的大小減少一并破壞堆結構，但如果我們使堆頂與堆尾的元素交換，我們就會有兩個好處：
一是可以把堆尾元素脫離堆（等效堆頂離堆）、并把它直接劃入有序區；
二是由于堆尾離堆而不是堆頂離堆，所以沒有破壞堆的結構，而且堆頂的子樹仍是堆，我們只要對堆頂的元素進行堆化就可以，不用像第一步那樣從后向前挨個兒堆化了，
怎么樣？是不是很妙？
4、代碼
1 import java.util.Arrays; 2 3 public class Main { 4 5 public static void heap_sort(int[] arr){ 6 //序列堆化,i指非葉子節點的下標 7 for (int i=arr.length/2-1 ; i>=0 ;i-- ){ 8 sort_node(arr,i,arr.length-1); 9 } 10 11 //交換堆頂堆尾，使堆尾脫離堆進入有序區，i指堆尾下標， 12 for(int i=arr.length-1 ; i>0 ; i--){ 13 // 堆頂的節點（最大值）與序列最后一個元素換位， 此時序列尾部逐漸有序化 14 int temp = arr[0]; 15 arr[0] = arr [i]; 16 arr[i] = temp; 17 //堆的規模開始減小,同時堆頂元素換了要進行維護 18 sort_node(arr,0,i-1); 19 } 20 } 21 22 /*對序列中某個節點進行堆化 23 * pointer指當前要堆化的節點 24 * end_edge指當前堆的最后一個節點 在 序列中的的下標 25 * */ 26 public static void sort_node (int[] arr, int pointer, int end_edge){ 27 int bigger_child ; 28 int left_child; 29 int right_child; 30 /* while的條件是判斷跳出遞回用的，不影響首次進入回圈，若當前節點是葉子節點時， 31 就不再對該的節點堆化并跳出回圈，由堆的性質可知，當左孩子為空時（即2*pointer+1越界）， 32 當前節點必然是葉子節點*/ 33 while (2*pointer+1 <= end_edge){ 34 left_child = 2*pointer+1; 35 right_child = 2*pointer+2; 36 if(right_child > end_edge){//單葉子的情況（只可能右為空） 37 bigger_child = left_child; 38 }else {//雙葉子的情況 39 bigger_child = arr[left_child]>arr[right_child]?left_child:right_child; 40 } 41 if(arr[pointer]<arr[bigger_child]){//判斷較大子孩子與父親的大小 42 //交換父子節點 43 int temp = arr[pointer]; 44 arr[pointer] = arr[bigger_child]; 45 arr[bigger_child] = temp; 46 pointer = bigger_child;//當前節點指標指向較大的孩子，遞回，對該節點進行堆化 47 }else { 48 break; 49 } 50 } 51 } 52 53 public static void main(String[] args) { 54 //測驗資料：5,6,9,8,7,4,1,2,3 55 int[] array = {5,6,4,45,1,2,33,6,7,99}; 56 heap_sort(array); 57 System.out.println(Arrays.toString(array)); 58 } 59 }
測驗結果：
最后，如果小伙伴覺得這篇博文對你有幫助的話，就點個推薦吧
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/10655.html
標籤：其他
上一篇：劍指offer-剪繩子1