數(shù)據(jù)結(jié)構(gòu)與算法之美-14講排序優(yōu)化：如何實(shí)現(xiàn)一個(gè)通用的、高性能的排序函數(shù)
特別備注
本系列非原創(chuàng)，文章原文摘自極客時(shí)間-數(shù)據(jù)結(jié)構(gòu)算法之美，用于平常學(xué)習(xí)記錄。如有侵權(quán)，請(qǐng)聯(lián)系我刪除，謝謝！
幾乎所有的編程語(yǔ)言都會(huì)提供排序函數(shù)，比如C語(yǔ)言中qsort()，C++ STL中的sort()、stable_sort()，還有Java語(yǔ)言中的Collections.sort()。在平時(shí)的開(kāi)發(fā)中，我們也都是直接使用這些現(xiàn)成的函數(shù)來(lái)實(shí)現(xiàn)業(yè)務(wù)邏輯中的排序功能。那你知道這些排序函數(shù)是如何實(shí)現(xiàn)的嗎？底層都利用了哪種排序算法呢？
基于這些問(wèn)題，今天我們就來(lái)看排序這部分的最后一塊內(nèi)容：如何實(shí)現(xiàn)一個(gè)通用的、高性能的排序函數(shù)？
如何選擇合適的排序算法？
如果要實(shí)現(xiàn)一個(gè)通用的、高效率的排序函數(shù)，我們應(yīng)該選擇哪種排序算法？我們先回顧一下前面講過(guò)的幾種排序算法。
我們前面講過(guò)，線性排序算法的時(shí)間復(fù)雜度比較低，適用場(chǎng)景比較特殊。所以如果要寫(xiě)一個(gè)通用的排序函數(shù)，不能選擇線性排序算法。
如果對(duì)小規(guī)模數(shù)據(jù)進(jìn)行排序，可以選擇時(shí)間復(fù)雜度是O(n2)的算法；如果對(duì)大規(guī)模數(shù)據(jù)進(jìn)行排序，時(shí)間復(fù)雜度是O(nlogn)的算法更加高效。所以，為了兼顧任意規(guī)模數(shù)據(jù)的排序，一般都會(huì)首選時(shí)間復(fù)雜度是O(nlogn)的排序算法來(lái)實(shí)現(xiàn)排序函數(shù)。
時(shí)間復(fù)雜度是O(nlogn)的排序算法不止一個(gè)，我們已經(jīng)講過(guò)的有歸并排序、快速排序，后面講堆的時(shí)候我們還會(huì)講到堆排序。堆排序和快速排序都有比較多的應(yīng)用，比如Java語(yǔ)言采用堆排序?qū)崿F(xiàn)排序函數(shù)，C語(yǔ)言使用快速排序?qū)崿F(xiàn)排序函數(shù)。
不知道你有沒(méi)有發(fā)現(xiàn)，使用歸并排序的情況其實(shí)并不多。我們知道，快排在最壞情況下的時(shí)間復(fù)雜度是O(n2)，而歸并排序可以做到平均情況、最壞情況下的時(shí)間復(fù)雜度都是O(nlogn)，從這點(diǎn)上看起來(lái)很誘人，那為什么它還是沒(méi)能得到“寵信”呢？
還記得我們上一節(jié)講的歸并排序的空間復(fù)雜度嗎？歸并排序并不是原地排序算法，空間復(fù)雜度是O(n)。所以，粗略點(diǎn)、夸張點(diǎn)講，如果要排序100MB的數(shù)據(jù)，除了數(shù)據(jù)本身占用的內(nèi)存之外，排序算法還要額外再占用100MB的內(nèi)存空間，空間耗費(fèi)就翻倍了。
前面我們講到，快速排序比較適合來(lái)實(shí)現(xiàn)排序函數(shù)，但是，我們也知道，快速排序在最壞情況下的時(shí)間復(fù)雜度是O(n2)，如何來(lái)解決這個(gè)“復(fù)雜度惡化”的問(wèn)題呢？
如何優(yōu)化快速排序？
我們先來(lái)看下，為什么最壞情況下快速排序的時(shí)間復(fù)雜度是O(n2)呢？我們前面講過(guò)，如果數(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)分開(kāi)的兩個(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ū)算法，你可以直觀地感受一下。
1.三數(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ù)取中”。
2.隨機(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é)講過(guò)，遞歸要警惕堆棧溢出。為了避免快速排序里，遞歸過(guò)深而堆棧過(guò)小，導(dǎo)致堆棧溢出，我們有兩種解決辦法：第一種是限制遞歸深度。一旦遞歸過(guò)深，超過(guò)了我們事先設(shè)定的閾值，就停止遞歸。第二種是通過(guò)在堆上模擬實(shí)現(xiàn)一個(gè)函數(shù)調(diào)用棧，手動(dòng)模擬遞歸壓棧、出棧的過(guò)程，這樣就沒(méi)有了系統(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è)問(wèn)題不大。現(xiàn)在計(jì)算機(jī)的內(nèi)存都挺大的，我們很多時(shí)候追求的是速度。還記得我們前面講過(guò)的用空間換時(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)致堆棧溢出的問(wèn)題，qsort()是通過(guò)自己實(shí)現(xiàn)一個(gè)堆上的棧，手動(dòng)模擬遞歸來(lái)解決的。我們之前在講遞歸那一節(jié)也講過(guò)，不知道你還有沒(méi)有印象？
實(shí)際上，qsort()并不僅僅用到了歸并排序和快速排序，它還用到了插入排序。在快速排序的過(guò)程中，當(dāng)要排序的區(qū)間中，元素的個(gè)數(shù)小于等于4時(shí)，qsort()就退化為插入排序，不再繼續(xù)用遞歸來(lái)做快速排序，因?yàn)槲覀兦懊嬉仓v過(guò)，在小規(guī)模數(shù)據(jù)面前，O(n2)時(shí)間復(fù)雜度的算法并不一定比O(nlogn)的算法執(zhí)行時(shí)間長(zhǎng)。我們現(xiàn)在就來(lái)分析下這個(gè)說(shuō)法。
我們?cè)谥v復(fù)雜度分析的時(shí)候講過(guò)，算法的性能可以通過(guò)時(shí)間復(fù)雜度來(lái)分析，但是，這種復(fù)雜度分析是比較偏理論的，如果我們深究的話，實(shí)際上時(shí)間復(fù)雜度并不等于代碼實(shí)際的運(yùn)行時(shí)間。
時(shí)間復(fù)雜度代表的是一個(gè)增長(zhǎng)趨勢(shì)，如果畫(huà)成增長(zhǎng)曲線圖，你會(huì)發(fā)現(xiàn)O(n2)比O(nlogn)要陡峭，也就是說(shuō)增長(zhǎng)趨勢(shì)要更猛一些。但是，我們前面講過(guò)，在大O復(fù)雜度表示法中，我們會(huì)省略低階、系數(shù)和常數(shù)，也就是說(shuō)，O(nlogn)在沒(méi)有省略低階、系數(shù)、常數(shù)之前可能是O(knlogn + c)，而且k和c有可能還是一個(gè)比較大的數(shù)。
假設(shè)k=1000，c=200，當(dāng)我們對(duì)小規(guī)模數(shù)據(jù)（比如n=100）排序時(shí)，n2的值實(shí)際上比knlogn+c還要小。
knlogn+c = 1000 * 100 * log100 + 200 遠(yuǎn)大于10000
n^2 = 100*100 = 10000
所以，對(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)化要做到極致。
好了，C語(yǔ)言的qsort()我已經(jīng)分析完了，你有沒(méi)有覺(jué)得其實(shí)也不是很難？基本上都是用了我們前面講到的知識(shí)點(diǎn)，有了前面的知識(shí)積累，看一些底層的類庫(kù)的時(shí)候是不是也更容易了呢？
內(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è)更加直觀的感受。
特別備注
本系列非原創(chuàng)，文章原文摘自極客時(shí)間-數(shù)據(jù)結(jié)構(gòu)算法之美，用于平常學(xué)習(xí)記錄。如有侵權(quán)，請(qǐng)聯(lián)系我刪除，謝謝！
