數(shù)據(jù)結(jié)構(gòu)與算法之美-14講排序優(yōu)化：如何實現(xiàn)一個通用的枫虏、高性能的排序函數(shù)
特別備注
本系列非原創(chuàng)，文章原文摘自極客時間-數(shù)據(jù)結(jié)構(gòu)算法之美隶债，用于平常學(xué)習(xí)記錄。如有侵權(quán)跑筝，請聯(lián)系我刪除，謝謝曲梗！
幾乎所有的編程語言都會提供排序函數(shù)，比如C語言中qsort()虏两，C++ STL中的sort()、stable_sort()定罢，還有Java語言中的Collections.sort()。在平時的開發(fā)中祖凫，我們也都是直接使用這些現(xiàn)成的函數(shù)來實現(xiàn)業(yè)務(wù)邏輯中的排序功能。那你知道這些排序函數(shù)是如何實現(xiàn)的嗎惠况？底層都利用了哪種排序算法呢？
基于這些問題稠屠，今天我們就來看排序這部分的最后一塊內(nèi)容：如何實現(xiàn)一個通用的峦睡、高性能的排序函數(shù)？
如何選擇合適的排序算法完箩？
如果要實現(xiàn)一個通用的、高效率的排序函數(shù)弊知，我們應(yīng)該選擇哪種排序算法？我們先回顧一下前面講過的幾種排序算法秩彤。
我們前面講過事哭，線性排序算法的時間復(fù)雜度比較低，適用場景比較特殊鳍咱。所以如果要寫一個通用的排序函數(shù)，不能選擇線性排序算法与柑。
如果對小規(guī)模數(shù)據(jù)進(jìn)行排序，可以選擇時間復(fù)雜度是O(n2)的算法价捧；如果對大規(guī)模數(shù)據(jù)進(jìn)行排序，時間復(fù)雜度是O(nlogn)的算法更加高效结蟋。所以，為了兼顧任意規(guī)模數(shù)據(jù)的排序嵌屎，一般都會首選時間復(fù)雜度是O(nlogn)的排序算法來實現(xiàn)排序函數(shù)。
時間復(fù)雜度是O(nlogn)的排序算法不止一個宝惰，我們已經(jīng)講過的有歸并排序、快速排序掌测，后面講堆的時候我們還會講到堆排序内贮。堆排序和快速排序都有比較多的應(yīng)用，比如Java語言采用堆排序?qū)崿F(xiàn)排序函數(shù)什燕，C語言使用快速排序?qū)崿F(xiàn)排序函數(shù)粘勒。
不知道你有沒有發(fā)現(xiàn)屎即，使用歸并排序的情況其實并不多。我們知道技俐，快排在最壞情況下的時間復(fù)雜度是O(n2)，而歸并排序可以做到平均情況雕擂、最壞情況下的時間復(fù)雜度都是O(nlogn)，從這點上看起來很誘人井赌，那為什么它還是沒能得到“寵信”呢贵扰？
還記得我們上一節(jié)講的歸并排序的空間復(fù)雜度嗎？歸并排序并不是原地排序算法戚绕，空間復(fù)雜度是O(n)。所以枝冀，粗略點、夸張點講果漾，如果要排序100MB的數(shù)據(jù)，除了數(shù)據(jù)本身占用的內(nèi)存之外跨晴，排序算法還要額外再占用100MB的內(nèi)存空間，空間耗費就翻倍了端盆。
前面我們講到，快速排序比較適合來實現(xiàn)排序函數(shù)焕妙，但是蒋伦，我們也知道焚鹊，快速排序在最壞情況下的時間復(fù)雜度是O(n2)，如何來解決這個“復(fù)雜度惡化”的問題呢末患？
如何優(yōu)化快速排序？
我們先來看下璧针，為什么最壞情況下快速排序的時間復(fù)雜度是O(n2)呢？我們前面講過探橱，如果數(shù)據(jù)原來就是有序的或者接近有序的，每次分區(qū)點都選擇最后一個數(shù)據(jù)隧膏，那快速排序算法就會變得非常糟糕，時間復(fù)雜度就會退化為O(n2)胞枕。實際上杆煞，這種O(n2)時間復(fù)雜度出現(xiàn)的主要原因還是因為我們分區(qū)點選的不夠合理。
那什么樣的分區(qū)點是好的分區(qū)點呢湖员？或者說如何來選擇分區(qū)點呢？
最理想的分區(qū)點是：被分區(qū)點分開的兩個分區(qū)中娘摔，數(shù)據(jù)的數(shù)量差不多。
如果很粗暴地直接選擇第一個或者最后一個數(shù)據(jù)作為分區(qū)點凳寺，不考慮數(shù)據(jù)的特點，肯定會出現(xiàn)之前講的那樣彤侍，在某些情況下，排序的最壞情況時間復(fù)雜度是O(n2)盏阶。為了提高排序算法的性能，我們也要盡可能地讓每次分區(qū)都比較平均名斟。
我這里介紹兩個比較常用、比較簡單的分區(qū)算法砰盐，你可以直觀地感受一下闷袒。
1.三數(shù)取中法
我們從區(qū)間的首囊骤、尾、中間冀值，分別取出一個數(shù)，然后對比大小列疗，取這3個數(shù)的中間值作為分區(qū)點。這樣每間隔某個固定的長度作彤，取數(shù)據(jù)出來比較乌逐，將中間值作為分區(qū)點的分區(qū)算法，肯定要比單純?nèi)∧骋粋€數(shù)據(jù)更好浙踢。但是，如果要排序的數(shù)組比較大，那“三數(shù)取中”可能就不夠了胰舆，可能要“五數(shù)取中”或者“十?dāng)?shù)取中”。
2.隨機(jī)法
隨機(jī)法就是每次從要排序的區(qū)間中缚窿，隨機(jī)選擇一個元素作為分區(qū)點。這種方法并不能保證每次分區(qū)點都選的比較好倦零，但是從概率的角度來看误续，也不大可能會出現(xiàn)每次分區(qū)點都選的很差的情況蹋嵌，所以平均情況下，這樣選的分區(qū)點是比較好的葫隙。時間復(fù)雜度退化為最糟糕的O(n2)的情況，出現(xiàn)的可能性不大恋脚。
好了，我這里也只是拋磚引玉慧起，如果想了解更多尋找分區(qū)點的方法，你可以自己課下深入去學(xué)習(xí)一下蚓挤。
我們知道，快速排序是用遞歸來實現(xiàn)的灿意。我們在遞歸那一節(jié)講過估灿，遞歸要警惕堆棧溢出缤剧。為了避免快速排序里，遞歸過深而堆棧過小荒辕，導(dǎo)致堆棧溢出，我們有兩種解決辦法：第一種是限制遞歸深度抵窒。一旦遞歸過深，超過了我們事先設(shè)定的閾值李皇，就停止遞歸削茁。第二種是通過在堆上模擬實現(xiàn)一個函數(shù)調(diào)用棧，手動模擬遞歸壓棧慰丛、出棧的過程，這樣就沒有了系統(tǒng)棧大小的限制诅病。
舉例分析排序函數(shù)
為了讓你對如何實現(xiàn)一個排序函數(shù)有一個更直觀的感受，我拿Glibc中的qsort()函數(shù)舉例說明一下富寿。雖說qsort()從名字上看，很像是基于快速排序算法實現(xiàn)的页徐，實際上它并不僅僅用了快排這一種算法。
如果你去看源碼变勇，你就會發(fā)現(xiàn)，qsort()會優(yōu)先使用歸并排序來排序輸入數(shù)據(jù)搀绣，因為歸并排序的空間復(fù)雜度是O(n)，所以對于小數(shù)據(jù)量的排序链患，比如1KB、2KB等麻捻，歸并排序額外需要1KB纲仍、2KB的內(nèi)存空間贸毕，這個問題不大。現(xiàn)在計算機(jī)的內(nèi)存都挺大的明棍，我們很多時候追求的是速度。還記得我們前面講過的用空間換時間的技巧嗎摊腋？這就是一個典型的應(yīng)用。
但如果數(shù)據(jù)量太大兴蒸，就跟我們前面提到的，排序100MB的數(shù)據(jù)类咧，這個時候我們再用歸并排序就不合適了。所以痕惋，要排序的數(shù)據(jù)量比較大的時候，qsort()會改為用快速排序算法來排序值戳。
那qsort()是如何選擇快速排序算法的分區(qū)點的呢？如果去看源碼堕虹，你就會發(fā)現(xiàn)卧晓，qsort()選擇分區(qū)點的方法就是“三數(shù)取中法”逼裆。是不是也并不復(fù)雜？
還有我們前面提到的遞歸太深會導(dǎo)致堆棧溢出的問題赦政，qsort()是通過自己實現(xiàn)一個堆上的棧，手動模擬遞歸來解決的恢着。我們之前在講遞歸那一節(jié)也講過，不知道你還有沒有印象掰派？
實際上，qsort()并不僅僅用到了歸并排序和快速排序靡羡，它還用到了插入排序。在快速排序的過程中亿眠，當(dāng)要排序的區(qū)間中碎罚，元素的個數(shù)小于等于4時纳像，qsort()就退化為插入排序，不再繼續(xù)用遞歸來做快速排序竟趾，因為我們前面也講過，在小規(guī)模數(shù)據(jù)面前岔帽，O(n2)時間復(fù)雜度的算法并不一定比O(nlogn)的算法執(zhí)行時間長。我們現(xiàn)在就來分析下這個說法犀勒。
我們在講復(fù)雜度分析的時候講過妥曲，算法的性能可以通過時間復(fù)雜度來分析，但是钦购，這種復(fù)雜度分析是比較偏理論的，如果我們深究的話押桃，實際上時間復(fù)雜度并不等于代碼實際的運行時間。
時間復(fù)雜度代表的是一個增長趨勢唱凯，如果畫成增長曲線圖，你會發(fā)現(xiàn)O(n2)比O(nlogn)要陡峭磕昼，也就是說增長趨勢要更猛一些。但是掰烟，我們前面講過爽蝴，在大O復(fù)雜度表示法中纫骑，我們會省略低階、系數(shù)和常數(shù)先馆，也就是說，O(nlogn)在沒有省略低階煤墙、系數(shù)、常數(shù)之前可能是O(knlogn + c)仿野，而且k和c有可能還是一個比較大的數(shù)铣减。
假設(shè)k=1000脚作，c=200，當(dāng)我們對小規(guī)模數(shù)據(jù)（比如n=100）排序時球涛，n2的值實際上比knlogn+c還要小。
knlogn+c = 1000 * 100 * log100 + 200 遠(yuǎn)大于10000
n^2 = 100*100 = 10000
所以亿扁，對于小規(guī)模數(shù)據(jù)的排序捺典，O(n2)的排序算法并不一定比O(nlogn)排序算法執(zhí)行的時間長襟己。對于小數(shù)據(jù)量的排序引谜，我們選擇比較簡單稀蟋、不需要遞歸的插入排序算法。
還記得我們之前講到的哨兵來簡化代碼退客，提高執(zhí)行效率嗎？在qsort()插入排序的算法實現(xiàn)中萌狂，也利用了這種編程技巧。雖然哨兵可能只是少做一次判斷茫藏，但是畢竟排序函數(shù)是非常常用、非撑恚基礎(chǔ)的函數(shù)，性能的優(yōu)化要做到極致枣申。
好了，C語言的qsort()我已經(jīng)分析完了忠藤，你有沒有覺得其實也不是很難？基本上都是用了我們前面講到的知識點模孩，有了前面的知識積累，看一些底層的類庫的時候是不是也更容易了呢榨咐？
內(nèi)容小結(jié)
今天我?guī)惴治隽艘幌氯绾蝸韺崿F(xiàn)一個工業(yè)級的通用的介却、高效的排序函數(shù)块茁，內(nèi)容比較偏實戰(zhàn)，而且貫穿了一些前面幾節(jié)的內(nèi)容龟劲，你要多看幾遍。我們大部分排序函數(shù)都是采用O(nlogn)排序算法來實現(xiàn)昌跌，但是為了盡可能地提高性能，會做很多優(yōu)化蚕愤。
我還著重講了快速排序的一些優(yōu)化策略答恶，比如合理選擇分區(qū)點、避免遞歸太深等等悬嗓。最后，我還帶你分析了一個C語言中qsort()的底層實現(xiàn)原理包竹，希望你對此能有一個更加直觀的感受。
特別備注
本系列非原創(chuàng)周瞎，文章原文摘自極客時間-數(shù)據(jù)結(jié)構(gòu)算法之美苗缩，用于平常學(xué)習(xí)記錄酱讶。如有侵權(quán)，請聯(lián)系我刪除彼乌，謝謝！
