c語言中sort()排序函數(shù)的實(shí)現(xiàn)。

實(shí)際上它并不僅僅用了快排這一種算法。

如果你去看源碼，你就會(huì)發(fā)現(xiàn)，sort()會(huì)優(yōu)先使用歸并排序來排序輸入數(shù)據(jù)，因?yàn)闅w并排序的時(shí)間復(fù)雜度，最好、最壞、平均都是O(nlogn)，而快排的時(shí)間復(fù)雜度最壞為O(n2)，雖然歸并排序的空間復(fù)雜度為O(n)，但對(duì)于小數(shù)據(jù)量的排序，比如1KB、2KB等，歸并排序額外需要1KB、2KB的內(nèi)存空間，這個(gè)問題不大?，F(xiàn)在計(jì)算機(jī)的內(nèi)存都挺大的，我們很多時(shí)候追求的是速度。還記得我們前面講過的用空間換時(shí)間的技巧嗎？這就是一個(gè)典型的應(yīng)用。

但如果數(shù)據(jù)量太大，就跟我們前面提到的，排序100MB的數(shù)據(jù)，這個(gè)時(shí)候我們?cè)儆脷w并排序就不合適了。所以，要排序的數(shù)據(jù)量比較大的時(shí)候，qsort()會(huì)改為用快速排序算法來排序。那sort()是如何選擇快速排序算法的分區(qū)點(diǎn)的呢？如果去看源碼，你就會(huì)發(fā)現(xiàn)，sort()選擇分區(qū)點(diǎn)的方法就是“三數(shù)取中法”。是不是也并不復(fù)雜？

還有我們前面提到的遞歸太深會(huì)導(dǎo)致堆棧溢出的問題，sort()是通過自己實(shí)現(xiàn)一個(gè)堆上的棧，手動(dòng)模擬遞歸來解決的。我們之前在講遞歸那一節(jié)也講過，不知道你還有沒有印象？實(shí)際上，sort()并不僅僅用到了歸并排序和快速排序，它還用到了插入排序。在快速排序的過程中，當(dāng)要排序的區(qū)間中，元素的個(gè)數(shù)小于等于4時(shí)，qsort()就退化為插入排序，不再繼續(xù)用遞歸來做快速排序，因?yàn)槲覀兦懊嬉仓v過，在小規(guī)模數(shù)據(jù)面前，O(n^2)時(shí)間復(fù)雜度的算法并不一定比O(nlogn)的算法執(zhí)行時(shí)間長(zhǎng)。我們現(xiàn)在就來分析下這個(gè)說法。

我們?cè)谥v復(fù)雜度分析的時(shí)候講過，算法的性能可以通過時(shí)間復(fù)雜度來分析，但是，這種復(fù)雜度分析是比較偏理論的，如果我們深究的話，實(shí)際上時(shí)間復(fù)雜度并不等于代碼實(shí)際的運(yùn)行時(shí)間。

時(shí)間復(fù)雜度代表的是一個(gè)增長(zhǎng)趨勢(shì)，如果畫成增長(zhǎng)曲線圖，你會(huì)發(fā)現(xiàn)O(n2)比O(nlogn)要陡峭，也就是說增長(zhǎng)趨勢(shì)要更猛一些。但是，我們前面講過，在大O復(fù)雜度表示法中，我們會(huì)省略低階、系數(shù)和常數(shù)，也就是說，O(nlogn)在沒有省略低階、系數(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)單、不需要遞歸的插入排序算法。

還記得我們之前講到的哨兵來簡(jiǎn)化代碼，提高執(zhí)行效率嗎？在sort()插入排序的算法實(shí)現(xiàn)中，也利用了這種編程技巧。雖然哨兵可能只是少做一次判斷，但是畢竟排序函數(shù)是非常常用、非?；A(chǔ)的函數(shù)，性能的優(yōu)化要做到極致。