? ? ? ? 幾乎所有的編程語言都會提供排序函數(shù)颠印，比如C語言中的qsort()纲岭，C++ STL中的sort()、stable_sort()线罕，還有Java語言中的Collections.sort()止潮。在平常的開發(fā)中我們也都是直接調用這些現(xiàn)成的排序函數(shù)來進行使用，但是這些函數(shù)是怎么實現(xiàn)的我們并不是很清楚钞楼。

? ? ? ? 這節(jié)課就要學習這些排序函數(shù)的底層實現(xiàn)利用了哪種排序算法沽翔。

? ? 1如何選擇合適的排序算法

? ? ? ? 下圖中使我們學過的排序算法的一個總結：

? ? ? ? 我們來分析一波~

? ? ? ? 對于線性排序算法計數(shù)排序、桶排序窿凤、基數(shù)排序，雖然它們的時間復雜度比較低跨蟹，但是它們適用場景比較特殊雳殊，對數(shù)據要求比較高，如果我們要寫一個通用的排序函數(shù)窗轩，肯定是不適合的夯秃，所以通用的排序函數(shù)一般不會選擇用線性排序算法來實現(xiàn)。

? ? ? ? 時間復雜度為O(n^2)的排序算法適用于小規(guī)模數(shù)據排序痢艺，時間復雜度為O(nlogn)的排序算法適用于大規(guī)模數(shù)據排序仓洼，一般情況下為了兼顧任意數(shù)據的排序，都會首選用時間復雜度是O(nlogn)的排序算法來實現(xiàn)排序函數(shù)堤舒。

? ? ? ? 因此通用的排序函數(shù)一般還是選擇時間復雜度為O(nlogn)的排序算法來實現(xiàn)色建，而時間復雜度為O(nlogn)的排序算法有歸并排序、快速排序舌缤，還有堆排序（后面會講）等等箕戳。其中堆排序和快速排序應用都比較多，比如Java語言采用堆排序實現(xiàn)排序函數(shù)国撵，C語言使用快速排序實現(xiàn)排序函數(shù)陵吸。

? ? ? ? 我們發(fā)現(xiàn)使用歸并排序的情況其實并不多，這是為什么捏介牙？

? ? ? ? 明明快排在最壞情況下的時間復雜度是O(n^2)壮虫，而歸并排序可以做到平均情況、最壞情況下的時間復雜度都是O(nlogn)环础，這不是很棒棒嗎囚似？但是它有一個很拖后腿的點：它不是原地排序算法，空間復雜度是O(n)喳整，夸張點講谆构，如果要排序100MB的數(shù)據，除了數(shù)據本身之外框都，排序算法還要額外再占用100MB的內存空間搬素，空間耗費就翻倍了呵晨。

? ? ? ? OK，分析完之后熬尺，我們知道快速排序和堆排序應用比較多摸屠，快速排序是我們前面學過的，今天就主要來說說它粱哼。剛剛有說到季二，快速排序在最壞情況下的時間復雜度是O(n^2)，那么我們該如何解決這個“復雜度惡化”的問題呢揭措？

????2如何優(yōu)化快速排序

? ? ? ? 先來說說為什么最壞情況下快速排序的時間復雜度是O(n^2)胯舷。

? ? ? ? 當要排序的數(shù)據原本就是有序的或者接近有序的時候，每次分區(qū)點都選擇最后一個數(shù)據绊含，排序算法就會變得非常糟糕桑嘶，時間復雜度就會退化為O(n^2)。

? ? ? ? 搬運一下之前的結論：

? ? ? ? 實際上躬充，這種O(n^2)時間復雜度出現(xiàn)的主要原因還是我們分區(qū)點選的不夠合理逃顶。

? ? ? ? 我們知道，理想的分區(qū)點是：被分區(qū)點分開的兩個分區(qū)中充甚，數(shù)據的數(shù)量差不多以政。

? ? ? ? 那么如何選擇一個合適的分區(qū)點呢？

? ? ? ? 下面簡單介紹兩個方法：

? ? ? ? 1.三數(shù)取中法

? ? ? ? 我們從區(qū)間的首伴找、尾盈蛮、中間，分別取出一個數(shù)疆瑰，然后對比它們的大小眉反，取這3個數(shù)的中間值作為分區(qū)點。如果要排序的數(shù)組比較大的話穆役，“三數(shù)取中”可能就不夠用了寸五，我們可以“五數(shù)取中”或者“十數(shù)取中”。

? ? ? ? 2.隨機法

? ? ? ? 每次從要排序的區(qū)間中耿币，隨機選擇一個元素作為分區(qū)點梳杏。這種方法并不能保證每次分區(qū)點都選的比較好，但是從概率的角度來看淹接，也不大可能會出現(xiàn)每次分區(qū)點都選得很差的情況十性，平均情況下這種選分區(qū)點的方法還是不錯的。

? ? ? ? 快速排序使用遞歸實現(xiàn)的塑悼，而用遞歸就要警惕堆棧溢出劲适。為了避免快速排序里遞歸過深而堆棧過小導致堆棧溢出，我們有兩種解決辦法：1.限制遞歸深度厢蒜。一旦遞歸過深霞势，超過了我們事先設定的閾值烹植，就停止遞歸。2.在堆上模擬實現(xiàn)一個函數(shù)調用棧愕贡，手動模擬遞歸壓棧草雕、出棧的過程。這樣就沒有了系統(tǒng)棧大小的限制固以。

? ? 3C語言中的qsort()分析

? ? ? ? 為了對如何實現(xiàn)衣蛾排序函數(shù)有更直觀的感受墩虹，下面我們拿C語言中的qsort()函數(shù)來分析一下。

? ? ? ? qsort()會優(yōu)先使用歸并排序來對輸入數(shù)據進行排序憨琳，因為歸并排序的空間復雜度是O(n)诫钓，所以對于小數(shù)據量的排序問題不大，而且現(xiàn)在計算機的內存都挺大的篙螟，我們很多時候更多的是追求速度尖坤。這就是我們之前提過的，用空間換時間闲擦。

? ? ? ? 但是如果數(shù)據量太大，qsort()就會改為用快速排序算法來排序场梆，并且它選擇分區(qū)點的方法是“三數(shù)取中”法墅冷。而且qsort()自己實現(xiàn)了一個堆上的棧，手動模擬遞歸或油，解決了遞歸太深會導致堆棧溢出的問題寞忿。

? ? ? ? 實際上，它還用到了插入排序顶岸。在快速排序的過程中腔彰，當要排序的區(qū)間中元素個數(shù)小于等于4時，qsort()就會變成使用插入排序辖佣，不再繼續(xù)用遞歸來做快速排序霹抛。因為在小規(guī)模數(shù)據面前，O(n^2)時間復雜度的算法并不一定比O(nlogn)的算法執(zhí)行時間長卷谈。

? ? ? ? 并且杯拐，qsort()用到了哨兵來簡化代碼提高執(zhí)行效率，雖然哨兵只是少做以此判斷世蔗，但是畢竟排序函數(shù)時非常常用端逼、非常基礎的函數(shù)污淋，性能的優(yōu)化要做到極致顶滩。

? ? 4內容小結

? ? ? ? 今天我們了解了如何實現(xiàn)一個工業(yè)級的通用的、高效的排序函數(shù)寸爆，我們大部分排序函數(shù)都是采用O(nlogn)時間復雜度的排序算法來實現(xiàn)礁鲁，但是為了盡可能地提高性能會做很多優(yōu)化盐欺。優(yōu)化策略包括但不限于：合理選擇分區(qū)點、避免堆棧溢出等等救氯。最后我們還分析了C語言的qsort()函數(shù)的底層實現(xiàn)原理找田。? ?

? ??????