排序優(yōu)化：如何實(shí)現(xiàn)一個(gè)通用的担神、高性能的排序函數(shù)
幾乎所有的編程語(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)景比較特殊这溅。所以如果要寫一個(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ū)算法，你可以直觀地感受一下往毡。
三數(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é)講過(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ì)著洼，如果畫成增長(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è)更加直觀的感受运杭。
課后思考
在今天的內(nèi)容中，我分析了 C 語(yǔ)言的中的 qsort() 的底層排序算法函卒，你能否分析一下你所熟悉的語(yǔ)言中的排序函數(shù)都是用什么排序算法實(shí)現(xiàn)的呢辆憔？都有哪些優(yōu)化技巧？
經(jīng)典評(píng)論
查看了下Arrays.sort的源碼，主要采用TimSort算法, 大致思路是這樣的：
1 元素個(gè)數(shù) < 32, 采用二分查找插入排序(Binary Sort)
2 元素個(gè)數(shù) >= 32, 采用歸并排序虱咧，歸并的核心是分區(qū)(Run)
3 找連續(xù)升或降的序列作為分區(qū)熊榛，分區(qū)最終被調(diào)整為升序后壓入棧
4 如果分區(qū)長(zhǎng)度太小，通過(guò)二分插入排序擴(kuò)充分區(qū)長(zhǎng)度到分區(qū)最小闕值
5 每次壓入棧腕巡，都要檢查棧內(nèi)已存在的分區(qū)是否滿足合并條件玄坦，滿足則進(jìn)行合并
6 最終棧內(nèi)的分區(qū)被全部合并，得到一個(gè)排序好的數(shù)組
Timsort的合并算法非常巧妙：
1 找出左分區(qū)最后一個(gè)元素(最大)及在右分區(qū)的位置
2 找出右分區(qū)第一個(gè)元素(最小)及在左分區(qū)的位置
3 僅對(duì)這兩個(gè)位置之間的元素進(jìn)行合并绘沉，之外的元素本身就是有序的
