如何實(shí)現(xiàn)一個(gè)通用的凿试、高性能的排序函數(shù)排宰？
如何選擇合適的排序算法似芝？
先回顧一下前面寫過的幾種排序算法：
線性排序算法的時(shí)間復(fù)雜度比較低，適用場景比較特殊板甘。所以寫一個(gè)通用的排序函數(shù)党瓮，不能選擇線性排序算法。
對小規(guī)模數(shù)據(jù)進(jìn)行排序盐类，可以選擇時(shí)間復(fù)雜度是 O(n^2) 的算法寞奸；如果對大規(guī)模數(shù)據(jù)進(jìn)行排序，時(shí)間復(fù)雜度是 O(nlogn)的算法更加高效在跳。所以枪萄，為了兼顧任意規(guī)模數(shù)據(jù)的排序，一般都會(huì)首選時(shí)間復(fù)雜度是 O(nlogn) 的排序算法來實(shí)現(xiàn)排序函數(shù)猫妙。
時(shí)間復(fù)雜度是 O(nlogn) 的排序算法不止一個(gè)瓷翻，有歸并排序、快速排序割坠、還有后面會(huì)講到的堆排序齐帚。堆排序和快速排序都有比較多的應(yīng)用，比如 Java 語言采用堆排序?qū)崿F(xiàn)排序函數(shù)彼哼，C 語言使用快速排序?qū)崿F(xiàn)排序函數(shù)对妄。
使用歸并排序的情況其實(shí)并不多。我們知道敢朱，快排在最壞情況下的時(shí)間復(fù)雜度是 剪菱，而歸并排序可以做到平均情況、最壞情況下的時(shí)間復(fù)雜度都是 O(nlogn)拴签，從這點(diǎn)上看起來很誘人孝常，為什么它還是沒能得到“寵信”呢？
歸并排序并不是原地排序算法篓吁，空間復(fù)雜度是 O(n)茫因。所以，粗略點(diǎn)講排序算法空間耗費(fèi)會(huì)翻倍杖剪。
快速排序比較適合來實(shí)現(xiàn)排序函數(shù)，但是驰贷，我們也知道盛嘿，快速排序在最壞情況下的時(shí)間復(fù)雜度是 ，如何來解決這個(gè)“復(fù)雜度惡化”的問題呢括袒？
如何優(yōu)化快速排序次兆？
為什么最壞情況下快速排序的時(shí)間復(fù)雜度是 呢？我們講過锹锰，如果數(shù)據(jù)原來就是有序的或者接近有序的芥炭，每次分區(qū)點(diǎn)都選擇最后一個(gè)數(shù)據(jù)漓库，那快速排序算法就會(huì)變得非常糟糕，時(shí)間復(fù)雜度就會(huì)退化為
园蝠。
實(shí)際上渺蒿，這種 時(shí)間復(fù)雜度出現(xiàn)的主要原因還是因?yàn)槲覀兎謪^(qū)點(diǎn)選的不夠合理。
那什么樣的分區(qū)點(diǎn)是好的分區(qū)點(diǎn)呢彪薛？或者說如何來選擇分區(qū)點(diǎn)呢茂装？最理想的分區(qū)點(diǎn)是：被分區(qū)點(diǎn)分開的兩個(gè)分區(qū)中，數(shù)據(jù)的數(shù)量差不多善延。
這里介紹兩個(gè)比較常用少态、比較簡單的分區(qū)算法，你可以直觀地感受一下易遣。
- 三數(shù)取中法
我們從區(qū)間的首彼妻、尾、中間豆茫，分別取出一個(gè)數(shù)侨歉，然后對比大小，取這 3 個(gè)數(shù)的中間值作為分區(qū)點(diǎn)澜薄。這樣每間隔某個(gè)固定的長度为肮，取數(shù)據(jù)出來比較，將中間值作為分區(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)都選的比較好，但是從概率的角度來看肯骇，也不大可能會(huì)出現(xiàn)每次分區(qū)點(diǎn)都選的很差的情況窥浪，所以平均情況下，這樣選的分區(qū)點(diǎn)是比較好的笛丙。時(shí)間復(fù)雜度退化為最糟糕的 的情況漾脂，出現(xiàn)的可能性不大。
如果想了解更多尋找分區(qū)點(diǎn)的方法胚鸯，可以自己課下深入去學(xué)習(xí)一下骨稿。
快排是遞歸來實(shí)現(xiàn)的，為了避免快速排序里遞歸過深而堆棧過小，導(dǎo)致堆棧溢出坦冠，有兩種解決辦法：
第一種是限制遞歸深度形耗。一旦遞歸過深，超過了我們事先設(shè)定的閾值辙浑，就停止遞歸激涤。
第二種是通過在堆上模擬實(shí)現(xiàn)一個(gè)函數(shù)調(diào)用棧，手動(dòng)模擬遞歸壓棧例衍、出棧的過程昔期，這樣就沒有了系統(tǒng)棧大小的限制填抬。
舉例分析排序函數(shù)
為了讓大家對如何實(shí)現(xiàn)一個(gè)排序函數(shù)有一個(gè)直觀的感受晚顷，拿 Glibc 中的 qsort() 函數(shù)舉例說明一下。雖說 qsort() 從名字上看鳍贾，很像是基于快速排序算法實(shí)現(xiàn)的梦抢，實(shí)際上它并不僅僅用了快排這一種算法般贼。
看源碼，你就會(huì)發(fā)現(xiàn)奥吩，qsort() 會(huì)優(yōu)先使用歸并排序來排序輸入數(shù)據(jù)哼蛆，因?yàn)闅w并排序的空間復(fù)雜度是 O(n)，所以對于小數(shù)據(jù)量的排序霞赫，比如 1KB腮介、2KB 等，歸并排序額外需要 1KB端衰、2KB 等叠洗，歸并排序額外需要 1KB、2KB 的內(nèi)存空間旅东，這個(gè)問題不大∶鹨郑現(xiàn)在計(jì)算機(jī)的內(nèi)存都挺大的，我們很多時(shí)候追求的是速度抵代。還記得我們前面講過的用空間換時(shí)間的技巧嗎腾节？這就是一個(gè)典型的應(yīng)用。
但如果數(shù)據(jù)量太大荤牍，就跟我們前面提到的案腺，排序 100MB 的數(shù)據(jù)，這個(gè)時(shí)候我們再用歸并排序就不合適了康吵。所以救湖，要排序的數(shù)據(jù)量比較大的時(shí)候，qsort() 會(huì)改為用快速排序算法來排序涎才。
那 qsort() 是如何選擇快速排序算法的分區(qū)點(diǎn)的呢？如果去看源碼，你就會(huì)發(fā)現(xiàn)耍铜，qsort() 選擇分區(qū)點(diǎn)的方法就是“三數(shù)取中法”邑闺。
還有我們前面提到的遞歸太深會(huì)導(dǎo)致堆棧溢出的問題，qsort() 是通過自己實(shí)現(xiàn)一個(gè)堆上的棧棕兼，手動(dòng)模擬遞歸來解決的陡舅。
實(shí)際上，qsort() 并不僅僅用到了歸并排序和快速排序伴挚，它還用到了插入排序靶衍。在快速排序的過程中，當(dāng)要排序的區(qū)間中茎芋，元素的個(gè)數(shù)小于等于 4 時(shí)颅眶，qsort() 就退化為插入排序，不再繼續(xù)用遞歸來做快速排序田弥，因?yàn)槲覀兦懊嬉仓v過涛酗，在小規(guī)模數(shù)據(jù)面前， 時(shí)間復(fù)雜度的算法并不一定比 O(nlogn) 的算法執(zhí)行時(shí)間長偷厦。我們現(xiàn)在就來分析下這個(gè)說法商叹。
算法的性能可以通過時(shí)間復(fù)雜度來分析，但是只泼，這種復(fù)雜度分析是比較偏理論的剖笙，如果我們深究的話，實(shí)際上時(shí)間復(fù)雜度并不等于代碼實(shí)際運(yùn)行時(shí)間请唱。
時(shí)間復(fù)雜度代表的是一個(gè)增長趨勢弥咪，如果畫成增長曲線圖，你會(huì)發(fā)現(xiàn) 比 O(nlogn) 要陡峭籍滴，也就是說增長趨勢要更猛一些酪夷。但是，我們前面講過孽惰，在大 O 復(fù)雜度表示法中晚岭，我們會(huì)省略低階、系數(shù)和常數(shù)勋功，也就是說坦报，O(nlogn) 在沒有省略低階、系數(shù)狂鞋、常數(shù)之前可能是 O(knlogn + c)片择，而且 k 和 c 有可能還是一個(gè)比較大的數(shù)。
假設(shè) k=1000骚揍，c=200字管，當(dāng)我們對小規(guī)模數(shù)據(jù)（比如 n=100）排序時(shí)啰挪， 的值實(shí)際上比 knlogn+c 還要小。
遠(yuǎn)大于 10000
所以嘲叔，對于小規(guī)模數(shù)據(jù)的排序亡呵， 的排序算法并不一定比 O(nlogn) 排序算法執(zhí)行的時(shí)間長。對于小數(shù)據(jù)量的排序硫戈，我們選擇比較簡單锰什、不需要遞歸的插入排序算法。
還記得我們之前講到的哨兵來簡化代碼丁逝，提高執(zhí)行效率嗎汁胆？在 qsort() 插入排序的算法實(shí)現(xiàn)中，也利用了這種編程技巧霜幼。雖然哨兵可能只是少做一次判斷嫩码，但是畢竟排序函數(shù)是非常常用、非承谅樱基礎(chǔ)的函數(shù)谢谦，性能的優(yōu)化要做到極致。
好了萝衩，C 語言的 qsort() 我已經(jīng)分析完了回挽，你有沒有覺得其實(shí)也不是很難？基本上都是用了我們前面講到的知識(shí)點(diǎn)猩谊，有了前面的知識(shí)積累千劈，看一些底層的類庫的時(shí)候是不是也更容易了呢？
小結(jié)
今天分析了一下如何來實(shí)現(xiàn)一個(gè)工業(yè)級(jí)的通用的牌捷、高效的排序函數(shù)墙牌，內(nèi)容比較偏實(shí)戰(zhàn)，而且貫穿了一些前面幾節(jié)的內(nèi)容暗甥，你要多看幾遍喜滨。我們大部分排序函數(shù)都是采用 O(nlogn) 排序算法來實(shí)現(xiàn)，但是為了盡可能地提高性能撤防，會(huì)做很多優(yōu)化虽风。
著重講了快速排序的一些優(yōu)化策略，比如合理選擇分區(qū)點(diǎn)寄月、避免遞歸太深等等辜膝。最后，還分析了一個(gè) C 語言中 qsort() 的底層實(shí)現(xiàn)原理漾肮，希望你對此能有一個(gè)更加直觀的感受厂抖。
課后思考
在今天的內(nèi)容中，我分析了 C 語言的中的 qsort() 的底層排序算法克懊，你能否分析一下你所熟悉的語言中的排序函數(shù)都是用什么排序算法實(shí)現(xiàn)的呢忱辅？都有哪些優(yōu)化技巧七蜘？
