浙江大學-數據結構-堆排序-9.3.2

堆排序

堆排序呢，其實是對選擇排序的一種改進，我們先看一個比較傻的演算法

就是一個非常直接了當的DeleteMin，這個Heap_Sort在一開始的時候，調用了一下BuildHeap這個函數，我們大家知道，有一種線性複雜度的演算法，可以把一個數組，直接調整成一個最小堆，調整好了以後，每次我就調用一個DeleteMin,把那個根結點給它彈出來，彈出來以後，我得有一個地方存，我需要另外開一個臨時的數組去存這些元素，總之我就一個一個把最小元彈出來，然後依次存到臨時數組裡面去(TmpA[i]),然後就完了嗎？沒完，我們最後必須把臨時數組裡的元素導回到A這個數組裡面去，因為我這個Heap_Sort默認的介面是什麼？你的用戶把一個無序的數組給了你，你在執行完了這個Sort之後，返回給它的必須是一個有序數組，而這個有序的數組還必須要存在原來的數組裡面，所以呢，光把這個TmpA生成了是不行的，你還得把TmpA裡面所有的元素導回到A裡面去

那這個其實就是挺浪費時間的一步了，那我們來看一下整體的時間複雜度是什麼呢？BuildHeap這一步，我們之前分析過，它是一個線性時間複雜度的，然後在這個循環裡面，每一步一個DeleteMin，我們知道O(logN)複雜度的，所以乘上這個外循環應該是NlogN,這一步應該是NlogN複雜度的，這一步單純的導一下，整體應該是O(N)複雜度的，所以全部加在一起，它的時間複雜度，應該是NlogN的，

這個演算法呢，看上去非常簡單，但是它有一個非常大的問題，它需要額外開一個O(N)數量級的空間，如果整個A的規模比較小，其實是沒有關係的，但是呢，如果你想像一下，你的內存如果一共有2GB,那本來你是可以對2GB的數據進行排序的，但是因為你要開額外的空間，導致你一次只能排1GB的東西，那這個時候就有問題了，你要排2GB的元素，你就開不出這個空間來，這個演算法就不能用了，另外複製這個元素，也是需要時間的，問題是，其實我們本來是沒有必要做這一步的，怎麼能把這一步跳過去呢？(for (i=0; i<N; i++)A[i] = TmpA[i];)

我們有更聰明的第二個演算法，要理解演算法2呢，我們還是先來看一個例子，比如說我們有一個數組，有4個元素，演算法2的一個想法是我不是要把它調整成一個最小堆，而是把它調整成一個最大堆，那怎麼調整呢？

從d,c這個子樹開始，然後再調整這棵子樹，

最後我們會得到這樣的一個結果，

d是a,b,c,d裡面最大的字母，然後它是處在根結點的位置，那因為我們知道d是最大的元素，而在一個正常排好序的數組裡面，最大元素應該放在哪呢？它應該是放在最後一個位置的，所以我們要做的就是把根結點跟最後一個結點做一個交換，把b放上去，把d放下來，放下來以後呢，我們就把整個堆的規模減1，我把d就排除在外了，因為後面再做什麼這個d都不用動了，它已經放在它最終的正確的位置上了，

然後我們再來看剩下的堆，剩下的堆還有3個元素，然後我要繼續把這個堆調整成一個最大堆，那麼這個是調整的結果，c應該在上面，

然後再重複前面的步驟，也就是把c換到現在最後一個位置上去，把c和a換一下位置，

然後把c也給砍掉，那現在的堆就只剩下a和b兩個元素，我們再把它調整成一個最大堆，然後b和a做最後一次交換，就完成了我們最後的排序

在之前講到堆這個概念的時候，我們說堆的元素是從第一個下標為1元素開始計數的，A[0]是不放任何真的元素的，A[0]裡面放的是哨兵，但是在我們排序的演算法裡頭，你的用戶可不知道在前面應該給你留個哨兵，你的用戶是從第0個元素就開始存的，所以在堆排序裡面的這個堆，它的元素是從0開始記的，那這也就導致了任何一個結點它跟它的孩子結點那個下標的關係就不一樣了，到底怎麼不一樣呢？我們來看一下真正的堆排序，它的偽代碼

那前面這一塊呢，實際上就是把BuildHeap這個函數寫的更具體了一點，它的核心呢，就是調用了一個PercDown,向下過濾的子函數，i對應的是根結點所在的位置，N對應的是當前這個堆裡面一共有多少個元素，從i=N/2開始，反覆的調用，就把一個最大堆建立起來了，然後就進入了我們的堆排序的循環，在這個循環里我們要做的是在我最大堆建立完了以後，我就知道A[0]這個根結點裡面一定存的是最大的元素，那麼我把它跟A[i],A[i]是什麼東西？i其實就記錄的當前的最後一個元素它的下標，我也就是把這個根結點，換到當前這個堆的最後一個元素的位置上去(Swap(&A[0], &A[i])),就相當於是一個DeleteMax這麼一個過程，然後呢，把剩下的元素繼續調整成一個最大堆，調整的時候呢，是以0為根結點，i是當前這個最大堆的元素的個數，這個Heap_Sort它的時間複雜度是什麼樣的呢？

所以它的平均比較次數仍然可以寫成O(NlogN),但是要比O(NlogN)要稍微好一點，因為還減去了一個參數，