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

堆排序

接下來給大家介紹的是堆排序，那要理解堆排序呢，我們先從選擇排序開始，選擇排序已經是一個老朋友了，我們在第一次課的時候，在講怎麼樣能夠用一個抽象的方法，去描述一個演算法的時候，就已經給大家講過這個選擇排序，選擇排序的英文叫做selection_sort,回顧一下，演算法講的是什麼呢？

就每次我們從i到N-1,這一段裡面去找一個最小元，把這個最小元的位置找到賦給這個變數，然後呢，我們就未排序部分的最小元換到有序部分的最後位置，那什麼是有序部分的最後位置呢，就是i這個位置，那我們就把找到的最小元換到i這個元素的位置上去，那這就完成了我們的選擇排序，那你要注意到說，當我們在交換這兩個元素的時候，Swap(A[i], A[MinPosition]),這兩個元素在大多數情況下，通常不是挨著的，它是可能跳了很遠的距離，做了一個交換，那麼這一次交換，就是一個好消息，我們可能一次交換就消掉了很多的逆序對，那我們要想一下，其實對於選擇排序而言，最壞情況下我們需要做多少次這個交換呢？反正我是找一個最小元，然後換一下，最壞情況是每次都必須換一下，那麼我最多需要換多少次呢?也就是循環了多少次我就需要換多少次，我最多就換n-1次，最後一個元素不用換，所以我們會看到交換這一部分的時間複雜度是線性的，是O(n),這是一個非常好的消息，但是，瓶頸在哪裡呢？瓶頸在這個函數

你要從A[i]到A[N-1]裡面找最小元，那我要怎麼做呢？選擇排序選擇的是一個簡單粗暴的方法，就是從A[i]一直掃描到A[N-1],每次都掃描一遍，然後把最小元挑出來，記到這裡面去，如果是這樣的話，那ScanForMin這個函數其實對應的也是一個for循環，那外面又套了一層for循環，於是很顯然，無論如何，它的時間複雜度，都是 這個數量級的，那它其實是無所謂最好情況還是最壞情況的，於是我們就想到想要得到一個更快的演算法，關鍵就在於如何把ScanForMin這一步變快，也就是說我們如何才能快速找到最小元呢？看見最小元這個詞你是不是應該馬上想到之前講過的一個很有用的工具，叫做最小堆，那最小堆的特點就是它的根結點，就一定存的是最小元，

所以就有了我們後面的堆排序