丨排序優(yōu)化如何實(shí)現(xiàn)一個(gè)通用的高性能函數(shù)

如果對小規(guī)模數(shù)據(jù)進(jìn)行排序，可以選擇時(shí)間復(fù)雜度是O(n2)的算法；如果對大規(guī)模數(shù)據(jù)進(jìn)行排序，時(shí)間復(fù)雜度是O(nlogn)的算法更加高效。所以，為了兼顧任意規(guī)模數(shù)據(jù)的排序，一般都會首選時(shí)間復(fù)雜度是O(nlogn)的排序算法來實(shí)現(xiàn)排序函數(shù)。時(shí)間復(fù)雜度是O(nlogn)的排序算法不止一個(gè)，我們已經(jīng)講過的有歸并排序、快速排序，后面講堆的時(shí)候我們還會講到堆排序。堆排序和快速排序都有比較多的應(yīng)用，比如Java語言采用堆排序?qū)崿F(xiàn)排序函數(shù)，C語言使用快速排序?qū)崿F(xiàn)排序函數(shù)。不知道你有沒有發(fā)現(xiàn)，使用歸并排序的情況其實(shí)并不多。我們知道，快排在情況下的時(shí)間復(fù)雜度是O(n2)，而歸并排序可以做到平均情況、情況下的時(shí)間復(fù)雜度都是O(nlogn)，從這點(diǎn)上看起來很，那為什么它還是沒能得到“寵信”呢？還記得我們上一節(jié)講的歸并排序的空間復(fù)雜度嗎？歸并排序并不是原地排序算法，空間復(fù)雜度是O(n)。所以，粗略點(diǎn)、夸張點(diǎn)講，如果要排序100MB的數(shù)據(jù)，除了數(shù)據(jù)本身占用的內(nèi)存之外，排序算法還要額外再占用100MB的內(nèi)存空間，空間耗費(fèi)就翻倍了。況下的時(shí)間復(fù)雜度是O(n2)，如何來解決這個(gè)“復(fù)雜度”的問題呢？我們先來看下，為什么情況下快速排序的時(shí)間復(fù)雜度是O(n2)呢？我們前面講過，如就會變得非常糟糕，時(shí)間復(fù)雜度就會為O(n2)。實(shí)際上，這種O(n2)時(shí)間復(fù)雜度出現(xiàn)那什么樣的分區(qū)點(diǎn)是好的分區(qū)點(diǎn)呢？或者說如何來選擇分區(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)，肯定會出現(xiàn)之前講的那樣，在某些情況下，排序的情況時(shí)間復(fù)雜度是O(2)。為了提高排序算法的性能，我們也要盡可能地讓每次分區(qū)都比較平均。我這里介紹兩個(gè)比較常用、比較簡單的分區(qū)算法，你可以直觀地感受一三數(shù)取我們從區(qū)間的首、尾、中間，分別取出一個(gè)數(shù)，然后對比大小，取這3個(gè)數(shù)的中間值作為肯定要比單純?nèi)∧骋粋€(gè)數(shù)據(jù)更好。但是，如果要排序的數(shù)組比較大，那“三數(shù)取中”可能就隨機(jī)隨機(jī)法就是每次從要排序的區(qū)間中，隨機(jī)選擇一個(gè)元素作為分區(qū)點(diǎn)。這種方法并不能保證每次分區(qū)點(diǎn)都選的比較好，但是從概率的角度來看，也不大可能會出現(xiàn)每次分區(qū)點(diǎn)都選的很差的情況，所以平均情況下，這樣選的分區(qū)點(diǎn)是比較好的。時(shí)間復(fù)雜度為最糟糕的O2)的情況，出現(xiàn)的可能性不大。我們知道，快速排序是用遞歸來實(shí)現(xiàn)的。我們在遞歸那一節(jié)講過，遞歸要警惕堆棧溢出。為了避免快速排序里，遞歸過深而堆棧過小，導(dǎo)致堆棧溢出，我們有兩種解決辦法：第一種是限制遞歸深度。一旦遞歸過深，超過了我們事先設(shè)定的閾值，就停止遞歸。第二種是通過在堆上模擬實(shí)現(xiàn)一個(gè)函數(shù)調(diào)用棧，手動模擬遞歸壓棧、出棧的過程，這樣就沒有了系統(tǒng)棧大小的限制。為了讓你對如何實(shí)現(xiàn)一個(gè)排序函數(shù)有一個(gè)更直觀的感受，我拿Glibc中的qsort()函數(shù)舉例說明一下。雖說qsort()從名字上看，很像是基于快速排序算法實(shí)現(xiàn)的，實(shí)際上它并不僅僅如果你去看源碼，你就會發(fā)現(xiàn)，qsort()會優(yōu)先使用歸并排序來排序輸入數(shù)據(jù)，因?yàn)闅w并排序的空間復(fù)雜度是O(n)，所以對于小數(shù)據(jù)量的排序，比如1KB、2KB等，歸并排序額外需要1KB、2KB的內(nèi)存空間，這個(gè)問題不大。現(xiàn)在計(jì)算機(jī)的內(nèi)存都挺大的，我們很多時(shí)候追但如果數(shù)據(jù)量太大，就跟我們前面提到的，排序100MB的數(shù)據(jù)，這個(gè)時(shí)候我們再用歸并排序就不合適了。所以，要排序的數(shù)據(jù)量比較大的時(shí)候，qsort()會改為用快速排序算法來排qsort如何選擇快速排序算法的分區(qū)點(diǎn)的呢？如果去看源碼，你就會發(fā)現(xiàn)，qsort()還有我們前面提到的遞歸太深會導(dǎo)致堆棧溢出的問題，qsort通過自己實(shí)現(xiàn)一個(gè)堆上的實(shí)際上，qsor()并不僅僅用到了歸并排序和快速排序，它還用到了插入排序。在快速排序的過程中，當(dāng)要排序的區(qū)間中，元素的個(gè)數(shù)小于等于4時(shí)，sort()就為插入排序，不再繼續(xù)用遞歸來做快速排序，因?yàn)槲覀兦懊嬉仓v過，在小規(guī)模數(shù)據(jù)面前，On2)時(shí)間復(fù)雜度的算法并不一定比O(nogn)的算法執(zhí)行時(shí)間長。我們現(xiàn)在就來分析下這個(gè)說法。我們在講復(fù)雜度分析的時(shí)候講過，算法的性能可以通過時(shí)間復(fù)雜度來分析，但是，這種復(fù)雜度分析是比較偏理論的，如果我們深究的話，實(shí)際上時(shí)間復(fù)雜度并不等于代碼實(shí)際的運(yùn)行時(shí)間。時(shí)間復(fù)雜度代表的是一個(gè)增長趨勢，如果畫成增長曲線圖，你會發(fā)現(xiàn)O(n2)比O(nlogn)要陡峭，也就是說增長趨勢要更猛一些。但是，我們前面講過，在大O復(fù)雜度表示法中，我們會省略低階、系數(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í)，n2的值實(shí)際上比knlogn+c還要小。代1knlogn+c=1000*100*log100+200遠(yuǎn)大于23n^2=100*100=所以，對于小規(guī)模數(shù)據(jù)的排序，O(n2)的排序算法并不一定比O(nlogn)排序算法執(zhí)行的時(shí)還記得我們之前講到的哨兵來簡化代碼，提高執(zhí)行效率嗎？在qsort插入排序的算法實(shí)現(xiàn)中，也利用了這種編程技巧。雖然哨兵可能只是少做一次判斷，但是畢竟排序函數(shù)是非常常用、非常基礎(chǔ)的函數(shù)，性能的優(yōu)化要做到極致。好了，C語言的sort我已經(jīng)分析完了，你有沒有覺得其實(shí)也不是很難？基本上都是用了我們前面講到的知識點(diǎn)，有了前面的知識積累，看一些底層的類庫的時(shí)候是不是也更容易了呢？O(nlogn)排序算法來實(shí)現(xiàn)，但是為了盡可能地提高性能，會做很多優(yōu)化。我還帶你分析了一個(gè)C語言中qsort()的底層實(shí)現(xiàn)原理，希望你對此能有一個(gè)更加直觀的在今天的內(nèi)容中，我分析了C言的中的qsort(底層排序算法，你能否分析一下你所歡迎留言和我，我會第一時(shí)間給你反饋特別說明專欄已經(jīng)更新一月有余，我在留言區(qū)看到很多同學(xué)說，希望給出課后思考題的標(biāo)準(zhǔn)答案。鑒于留言區(qū)里本身就有很多非常好的答案，之后我會將我認(rèn)為比較好的答案置頂在留言區(qū)，供需要的同學(xué)參考。最后，希望你把思考的過程看得比標(biāo)準(zhǔn)答案更重 歸科技所有 不得售賣。頁面已增加防盜追蹤，將依法其上一 13|線性排序：如何根據(jù)給100萬用戶數(shù)據(jù)排序下一 15|二分查找（上）：如何用最省內(nèi)存的方式實(shí)現(xiàn)快速查找功能言精選留言言

177展 88查看了下Arrays.sort的源碼，主要采用TimSort132,采用二分查找插入排序(Binary2元素個(gè)數(shù)>=32,采用歸并排序，歸并的是分區(qū)展楊 展小確 39數(shù)據(jù)庫里面的OrderBY展峰 展姜 冒泡排序O(n^2)是是…展Andrew陳 的，但當(dāng)遞歸深度過大時(shí)會轉(zhuǎn)為使用歸并排序。但是歸并排序也是遞歸排