回顧一下堆排的過程：
建立最大堆（堆頂?shù)脑卮笥谄鋬蓚€兒子，兩個兒子又分別大于它們各自下屬的兩個兒子… 以此類推）
將堆頂?shù)脑睾妥詈笠粋€元素對調(diào)（相當(dāng)于將堆頂元素（最大值）拿走，然后將堆底的那個元素補(bǔ)上它的空缺）扔字，然后讓那最后一個元素從頂上往下滑到恰當(dāng)?shù)奈恢茫ㄖ匦率苟炎畲蠡?/p>
重復(fù)第2步。
這里的關(guān)鍵問題就在于第2步，堆底的元素肯定很小抛虏，將它拿到堆頂和原本屬于最大元素的兩個子節(jié)點比較沸毁，它比它們大的可能性是微乎其微的。實際上它肯定小于其中的一個兒子。而大于另一個兒子的可能性非常小。于是，這一次比較的結(jié)果就是概率不均等的凯旋，根據(jù)前面的分析荒椭，概率不均等的比較是不明智的味悄，因為它并不能保證在糟糕情況下也能將問題的可能性削減到原本的1/2费韭《皆荩可以想像一種極端情況，如果a肯定小于b伟墙，那么比較a和b就會什么信息也得不到——原本剩下多少可能性還是剩下多少可能性生蚁。
在堆排里面有大量這種近乎無效的比較志衣，因為被拿到堆頂?shù)哪莻€元素幾乎肯定是很小的和二，而靠近堆頂?shù)脑赜謳缀蹩隙ㄊ呛艽蟮难推牵瑢⒁粋€很小的數(shù)和一個很大的數(shù)比較，結(jié)果幾乎肯定是“小于”的驶社，這就意味著問題的可能性只被排除掉了很小一部分恕汇。
這就是為什么堆排比較慢（堆排雖然和快排一樣復(fù)雜度都是O(NlogN)但堆排復(fù)雜度的常系數(shù)更大）。
一種Fast-HeapSort:
1瓣赂、將堆頂?shù)脑啬玫簟?br>
2妓肢、每次不是將堆底的元素拿到上面去卷拘，而是直接比較堆頂（最大）元素的兩個兒子栗弟，即選出次大的元素，補(bǔ)充到堆頂
3惋增、類似于步驟2纫塌，重復(fù)利用兒子節(jié)點的較大元素補(bǔ)充父親節(jié)點胸嘁，直至葉節(jié)點。
參考：
http://mindhacks.cn/2008/06/13/why-is-quicksort-so-quick/
https://www.zhihu.com/question/20842649
https://blog.csdn.net/tiandawenwu/article/details/17926581
