如何選擇合適的排序算法？
如果要實(shí)現(xiàn)一個(gè)通用的、高效率的排序函數(shù)，我們應(yīng)該選擇哪種排序算法？我們先回顧一下前面講過的幾種排序算法。
如何優(yōu)化快速排序？
我們先來(lái)看下，為什么最壞情況下快速排序的時(shí)間復(fù)雜度是 O(n2) 呢？我們前面講過，如果數(shù)據(jù)原來(lái)就是有序的或者接近有序的，每次分區(qū)點(diǎn)都選擇最后一個(gè)數(shù)據(jù)，那快速排序算法就會(huì)變得非常糟糕，時(shí)間復(fù)雜度就會(huì)退化為 O(n2)。實(shí)際上，這種 O(n2) 時(shí)間復(fù)雜度出現(xiàn)的主要原因還是因?yàn)槲覀兎謪^(qū)點(diǎn)選得不夠合理。那什么樣的分區(qū)點(diǎn)是好的分區(qū)點(diǎn)呢？或者說(shuō)如何來(lái)選擇分區(qū)點(diǎn)呢？最理想的分區(qū)點(diǎn)是：被分區(qū)點(diǎn)分開的兩個(gè)分區(qū)中，數(shù)據(jù)的數(shù)量差不多。如果很粗暴地直接選擇第一個(gè)或者最后一個(gè)數(shù)據(jù)作為分區(qū)點(diǎn)，不考慮數(shù)據(jù)的特點(diǎn)，肯定會(huì)出現(xiàn)之前講的那樣，在某些情況下，排序的最壞情況時(shí)間復(fù)雜度是 O(n2)。為了提高排序算法的性能，我們也要盡可能地讓每次分區(qū)都比較平均。我這里介紹兩個(gè)比較常用、比較簡(jiǎn)單的分區(qū)算法，你可以直觀地感受一下。
三數(shù)取中法
我們從區(qū)間的首、尾、中間，分別取出一個(gè)數(shù)，然后對(duì)比大小，取這 3 個(gè)數(shù)的中間值作為分區(qū)點(diǎn)。這樣每間隔某個(gè)固定的長(zhǎng)度，取數(shù)據(jù)出來(lái)比較，將中間值作為分區(qū)點(diǎn)的分區(qū)算法，肯定要比單純?nèi)∧骋粋€(gè)數(shù)據(jù)更好。但是，如果要排序的數(shù)組比較大，那“三數(shù)取中”可能就不夠了，可能要“五數(shù)取中”或者“十?dāng)?shù)取中”。隨機(jī)法
隨機(jī)法就是每次從要排序的區(qū)間中，隨機(jī)選擇一個(gè)元素作為分區(qū)點(diǎn)。這種方法并不能保證每次分區(qū)點(diǎn)都選的比較好，但是從概率的角度來(lái)看，也不大可能會(huì)出現(xiàn)每次分區(qū)點(diǎn)都選得很差的情況，所以平均情況下，這樣選的分區(qū)點(diǎn)是比較好的。時(shí)間復(fù)雜度退化為最糟糕的 O(n2) 的情況，出現(xiàn)的可能性不大。好了，我這里也只是拋磚引玉，如果想了解更多尋找分區(qū)點(diǎn)的方法，你可以自己課下深入去學(xué)習(xí)一下。我們知道，快速排序是用遞歸來(lái)實(shí)現(xiàn)的。我們?cè)谶f歸那一節(jié)講過，遞歸要警惕堆棧溢出。為了避免快速排序里，遞歸過深而堆棧過小，導(dǎo)致堆棧溢出，我們有兩種解決辦法：第一種是限制遞歸深度。一旦遞歸過深，超過了我們事先設(shè)定的閾值，就停止遞歸。第二種是通過在堆上模擬實(shí)現(xiàn)一個(gè)函數(shù)調(diào)用棧，手動(dòng)模擬遞歸壓棧、出棧的過程，這樣就沒有了系統(tǒng)棧大小的限制。
舉例分析排序函數(shù)
為了讓你對(duì)如何實(shí)現(xiàn)一個(gè)排序函數(shù)有一個(gè)更直觀的感受，我拿 Glibc 中的 qsort() 函數(shù)舉例說(shuō)明一下。雖說(shuō) qsort() 從名字上看，很像是基于快速排序算法實(shí)現(xiàn)的，實(shí)際上它并不僅僅用了快排這一種算法。
如果你去看源碼，你就會(huì)發(fā)現(xiàn)，qsort() 會(huì)優(yōu)先使用歸并排序來(lái)排序輸入數(shù)據(jù)，因?yàn)闅w并排序的空間復(fù)雜度是 O(n)，所以對(duì)于小數(shù)據(jù)量的排序，比如 1KB、2KB 等，歸并排序額外需要 1KB、2KB 的內(nèi)存空間，這個(gè)問題不大?，F(xiàn)在計(jì)算機(jī)的內(nèi)存都挺大的，我們很多時(shí)候追求的是速度。還記得我們前面講過的用空間換時(shí)間的技巧嗎？這就是一個(gè)典型的應(yīng)用。
但如果數(shù)據(jù)量太大，就跟我們前面提到的，排序 100MB 的數(shù)據(jù)，這個(gè)時(shí)候我們?cè)儆脷w并排序就不合適了。所以，要排序的數(shù)據(jù)量比較大的時(shí)候，qsort() 會(huì)改為用快速排序算法來(lái)排序。
那 qsort() 是如何選擇快速排序算法的分區(qū)點(diǎn)的呢？如果去看源碼，你就會(huì)發(fā)現(xiàn)，qsort() 選擇分區(qū)點(diǎn)的方法就是“三數(shù)取中法”。是不是也并不復(fù)雜？
還有我們前面提到的遞歸太深會(huì)導(dǎo)致堆棧溢出的問題，qsort() 是通過自己實(shí)現(xiàn)一個(gè)堆上的棧，手動(dòng)模擬遞歸來(lái)解決的。我們之前在講遞歸那一節(jié)也講過，不知道你還有沒有印象？
實(shí)際上，qsort() 并不僅僅用到了歸并排序和快速排序，它還用到了插入排序。在快速排序的過程中，當(dāng)要排序的區(qū)間中，元素的個(gè)數(shù)小于等于 4 時(shí)，qsort() 就退化為插入排序，不再繼續(xù)用遞歸來(lái)做快速排序，因?yàn)槲覀兦懊嬉仓v過，在小規(guī)模數(shù)據(jù)面前，O(n2) 時(shí)間復(fù)雜度的算法并不一定比 O(nlogn) 的算法執(zhí)行時(shí)間長(zhǎng)。
我們現(xiàn)在就來(lái)分析下這個(gè)說(shuō)法。我們?cè)谥v復(fù)雜度分析的時(shí)候講過，算法的性能可以通過時(shí)間復(fù)雜度來(lái)分析，但是，這種復(fù)雜度分析是比較偏理論的，如果我們深究的話，實(shí)際上時(shí)間復(fù)雜度并不等于代碼實(shí)際的運(yùn)行時(shí)間。
時(shí)間復(fù)雜度代表的是一個(gè)增長(zhǎng)趨勢(shì)，如果畫成增長(zhǎng)曲線圖，你會(huì)發(fā)現(xiàn) O(n2) 比 O(nlogn) 要陡峭，也就是說(shuō)增長(zhǎng)趨勢(shì)要更猛一些。但是，我們前面講過，在大 O 復(fù)雜度表示法中，我們會(huì)省略低階、系數(shù)和常數(shù)，也就是說(shuō)，O(nlogn) 在沒有省略低階、系數(shù)、常數(shù)之前可能是 O(knlogn + c)，而且 k 和 c 有可能還是一個(gè)比較大的數(shù)。
所以，對(duì)于小規(guī)模數(shù)據(jù)的排序，O(n2) 的排序算法并不一定比 O(nlogn) 排序算法執(zhí)行的時(shí)間長(zhǎng)。對(duì)于小數(shù)據(jù)量的排序，我們選擇比較簡(jiǎn)單、不需要遞歸的插入排序算法。
還記得我們之前講到的哨兵來(lái)簡(jiǎn)化代碼，提高執(zhí)行效率嗎？在 qsort() 插入排序的算法實(shí)現(xiàn)中，也利用了這種編程技巧。雖然哨兵可能只是少做一次判斷，但是畢竟排序函數(shù)是非常常用、非常基礎(chǔ)的函數(shù)，性能的優(yōu)化要做到極致。
內(nèi)容小結(jié)
今天我?guī)惴治隽艘幌氯绾蝸?lái)實(shí)現(xiàn)一個(gè)工業(yè)級(jí)的通用的、高效的排序函數(shù)，內(nèi)容比較偏實(shí)戰(zhàn)，而且貫穿了一些前面幾節(jié)的內(nèi)容，你要多看幾遍。我們大部分排序函數(shù)都是采用 O(nlogn) 排序算法來(lái)實(shí)現(xiàn)，但是為了盡可能地提高性能，會(huì)做很多優(yōu)化。我還著重講了快速排序的一些優(yōu)化策略，比如合理選擇分區(qū)點(diǎn)、避免遞歸太深等等。最后，我還帶你分析了一個(gè) C 語(yǔ)言中 qsort() 的底層實(shí)現(xiàn)原理，希望你對(duì)此能有一個(gè)更加直觀的感受。
參考
14 | 排序優(yōu)化：如何實(shí)現(xiàn)一個(gè)通用的、高性能的排序函數(shù)？ https://time.geekbang.org/column/article/42359
