標籤：

堆排序缺點何在？

01-05

最近在看coursera上的演算法課，裡面講堆排序那集，最後提到，heap sort 「make poor use of cache memory". 想了一下不太懂。他好像是拿堆排序跟快速排序作對比地說。

鏈接 ： Algorithms, Part I

最後面他的解釋，不甚明白。 為什麼比快排 make poor use of cache memory？

（謝謝邀請）

平均時間上，堆排序的時間常數比快排要大一些，因此通常會慢一些，但是堆排序最差時間也是O(nlogn)的，這點比快排好。

關於 poor use of cache memory，我的理解是快排在遞歸進行部分的排序的時候，只會訪問局部的數據，因此緩存能夠更大概率的命中；而堆排序的建堆過程是整個數組各個位置都訪問到的，後面則是所有未排序數據各個位置都可能訪問到的，所以不利於緩存發揮作用。簡答的說就是快排的存取模型的局部性（locality）更強，堆排序差一些。

我理解，速度和緩存的問題都反映了堆排序讓數據過於大距離的移動，你觀察某個元素在整個排序過程中的移動過程，會發現它是前後大幅度的跑動；而快速排序則是儘快的移動到最終的位置，然後做小範圍的跳動。

下面是10個隨機數進行快速排序和堆排序的過程，你可以盯著某個元素往下看，會發現堆排序中，一些元素在左右亂跳，而快速排序中這樣的情況會少很多。（數據產生的 Go 源代碼在這裡： Path of quick-sort and heap sort.）

Data {9 4 2 6 8 0 3 1 7 5}
Index [0 1 2 3 4 5 6 7 8 9]

Quick-sort
[[0 1 2 3 4 5 6 7 8 9]
[9 1 2 3 4 5 6 7 8 0]
[9 1 2 7 4 5 6 3 8 0]
[9 1 2 7 6 5 4 3 8 0]
[5 1 2 7 6 9 4 3 8 0]
[5 1 2 7 6 9 3 4 8 0]
[5 1 2 7 6 9 3 8 4 0]
[5 2 1 7 6 9 3 8 4 0]
[5 2 7 1 6 9 3 8 4 0]
[5 7 2 1 6 9 3 8 4 0]
[5 7 2 6 1 9 3 8 4 0]](11x10)

Heap-sort
[[0 1 2 3 4 5 6 7 8 9]
[0 1 2 8 4 5 6 7 3 9]
[0 1 6 8 4 5 2 7 3 9]
[0 4 6 8 1 5 2 7 3 9]
[0 4 6 8 9 5 2 7 3 1]
[1 4 6 8 9 5 2 7 3 0]
[4 1 6 8 9 5 2 7 3 0]
[4 8 6 1 9 5 2 7 3 0]
[4 8 6 3 9 5 2 7 1 0]
[1 8 6 3 9 5 2 7 4 0]
[8 1 6 3 9 5 2 7 4 0]
[8 3 6 1 9 5 2 7 4 0]
[7 3 6 1 9 5 2 8 4 0]
[3 7 6 1 9 5 2 8 4 0]
[3 9 6 1 7 5 2 8 4 0]
[2 9 6 1 7 5 3 8 4 0]
[9 2 6 1 7 5 3 8 4 0]
[9 1 6 2 7 5 3 8 4 0]
[5 1 6 2 7 9 3 8 4 0]
[1 5 6 2 7 9 3 8 4 0]
[1 2 6 5 7 9 3 8 4 0]
[7 2 6 5 1 9 3 8 4 0]
[6 2 7 5 1 9 3 8 4 0]
[5 2 7 6 1 9 3 8 4 0]
[2 5 7 6 1 9 3 8 4 0]
[7 5 2 6 1 9 3 8 4 0]
[5 7 2 6 1 9 3 8 4 0]](27x10)

關於cache locality，如果願意看c++的話可以看這個：

http://m.youtube.com/watch?v=L7zSU9HI-6I

簡言之快排是順著掃的，堆排序是跳著走的。

快排比堆排序快還有個原因，就是平均情況下堆排序更接近n lg n，而快排要好些。詳見這篇：

數學之美番外篇：快排為什麼那樣快

這個遠優於是不是有欠考慮，內核裡面的sort就是用堆排序寫的。

貼一段注釋

../linux-3.14.13/lib/sort.c:

/**
* sort - sort an array of elements
* @base: pointer to data to sort
* @num: number of elements
* @size: size of each element
* @cmp_func: pointer to comparison function
* @swap_func: pointer to swap function or NULL
*
* This function does a heapsort on the given array. You may provide a
* swap_func function optimized to your element type.
*
* Sorting time is O(n log n) both on average and worst-case. While
* qsort is about 20% faster on average, it suffers from exploitable
* O(n*n) worst-case behavior and extra memory requirements that make
* it less suitable for kernel use.
*/

一般來說快排要優於堆排。

要說堆排差在哪裡，我覺得可能是：每次移出堆頂最大元素後，都需要從頂部維護最大堆性質導致了過多的數據交換操作。

空間複雜度

堆排和快排都是原址排序演算法，即除了輸入數組外，僅需要常數個額外的存儲空間。

空間複雜度都是 O(1) 。

時間複雜度

堆排的時間複雜度跟演算法相關，比較穩定。因為不管數據如何，堆排都要先構造最大堆，然後一個一個的把堆頂元素移到堆尾，之後再維持最大堆的性質。具體演算法見：排序演算法-堆排序

而快排的時間複雜度受數據的印象。但一般情況下都不會差到哪裡去。下面我們會說。

不管是以上那種排序演算法，都涉及到交換數組中兩個數據的位置。

我剛才寫了個隨機模擬程序：

分別使用堆排、快排對 20個、100 個、1000個隨機數據進行排序，並記錄平均交換數據的次數。

數組大小 20 100 1000

堆排序 78 588 6017

快排 28 271 3996

隨機試驗結果來看，快排的確比堆排好。

關於快排的不穩定

我們常說快排不穩定，跟數據有關，最壞運行時間是 O({n}^{2}) ，那什麼情況下才會發生？

了解快排的同學應該知道，快排其實是把數組按照某個基準數據 a 進行分割，分為大於 a 的數據（放右邊）和小於 a 的數據（放左邊），接著把 a 放中間；然後對左右分別遞歸此過程。

那麼只有當每次分割數據時，所有數據都小於 a ，或者都大於 a 時，才會產生 O({n}^{2}) 的時間複雜度。

分割操作的時間複雜度是 O(n)

所以時間複雜度為： T(n) = T(n-1) + O(n)=O({n}^{2})

發生這種情況的概率是： frac{1}{n!} ，約等於0.

從統計學上來說，快排產生的劃分 80% 以上都比 9:1 更平衡，另外的 20% 的劃分比 9:1 更不平衡。就算所有的劃分都是 9:1 ，快排的時間複雜度依然是 O(nlgn) .

17-08-20 更新：

上述回答沒有怎麼對 heap sort 「make poor use of cache memory" 做解釋，是因為自己也沒有想太明白。

剛才在《演算法導論》上看基數排序是也看到了這麼一句話：快速排序通常比基數排序更有效地舒勇硬體的緩存。

仔細想一想，快排除了數據交換操作少之外，它的循環比價操作是拿 array[i] 與k ，進行比較，其中 i 是循環的下標， k 是選中的基準點，一般選 array 首部或尾部。

而堆排序比較的是 array[i] 、 array[left(i)] 與 array[right[i]] 。

在硬體基礎上，快排的基準點 k 每次循環時都要訪問，更容易緩存命中，但堆排的中的數據相比來說沒那麼容易。所以說 heap sort 「make poor use of cache memory"。

跟快排做對比的話

空間對比

快排需要用 n * meta數據的內存

堆需要2 * n * meta 數據的內存（因為堆的二分合併操作需要兩個不同的數據空間，why，自己看課本）

make poor use of cache memory的意思就是堆排序的內存佔用是快排的兩倍

時間對比

快排是非穩定時間的，堆排序是穩定時間的，堆排序的排序時間與數據無關，快排與數據有關，（堆排序對相同長度的數組比較次數是固定的，這點估計在教材某個角落沒注意吧？）意味著同樣大小的數據，可能已經排好序的，堆排序仍然需要花上同樣的時間去排序，大部分情況下快排比堆排序要快

所以由統計學意義來講，快排遠比堆要優越

推薦閱讀：

※從N個數組中找出出現最多的前K個數？
※為什麼Windows系統自帶的記事本(notepad.exe)程序打開大文件這麼慢？
※有沒有什麼演算法可以確定兩圖是否同構？
※N個數最少比較多少次才能保證知道大小順序?
※演算法要怎麼學好？

TAG:演算法 | 排序演算法 | 堆排序 |