說到快我只推崇葵花寶典，那叫一個快啊～～～
皮一下哈哈，言歸正傳。快速排序算法如其名一樣，快！來看看快排和其他幾大排序算法的并行運行對比視頻（中間那個就是快排），你就知道它到底有多快了，請全屏橫屏播放更清晰：
代碼如下：
typedef int T_ELEMENT;
int partition(T_ELEMENT A[ ], int left, int right);
/* sort A[left..right] */
void quicksort(T_ELEMENT A[ ], int left, int right)
{
int q;
if( right <= left )
return;
if ( right > left )
{
q = partition(A, left, right);
/* partition分塊后 */
//-> A[left..q-1] ≤ A[q] ≤ A[q+1..right]
quicksort(A, left, q-1);
quicksort(A, q+1, right);
}
}
int partition(T_ELEMENT A[], int left, int right);
{
T_ELEMENT P = A[left];
i = left;
j = right + 1;
/*無限循環,使用break退出*/
for(;;)
{
while (A[++i] < P) if (i >= right) break;
/* 此時 A[i] ≥ P */
while (A[--j] > P) if (j <= left) break;
/* 此時 A[j] ≤ P */
if (i >= j ) break; /*退出for循環*/
else swap(A[i], A[j]);
}
if (j == left) return j ;
swap(A[left], A[j]);
return j;
}
舉栗子分析:
分成三塊了,再遞歸子塊迭代,直到right<=left. 這里放一個全過程慢鏡頭動圖，幫助理解：
T(n) = θ(n) + T(i) + T(n-i-1) = cn+ T(i) + T(n-i-1)
其中，i是分區后第一個子塊的大小，將T(0)=T(1)= 1作為初始條件。
如果這種情況在每個分區中都重復發生，那么每個遞歸調用處理一個比前一個列表小1的列表。因此需要在達到大小為1的列表之前進行n - 1次嵌套調用。這意味著調用樹是n - 1個嵌套調用的線性鏈。第i次調用需要做O(n-i)復雜度來進行分區，則
如每次分區時樞軸(pivot)都能取到中間值，即每次分區后，將產生兩個大小大致相等的子塊，并且樞軸(pivot)元素處于中間值位置，需要做n次比較運算。
遞歸方程：
如前所說，如每次執行分區時，都能將列表分成兩個幾乎相等的兩個子塊。這意味著每次遞歸調用都要處理一個只有一半大小的列表。因此，在到達大小為1的列表之前，我們只能進行 嵌套調用。這意味著調用樹的深度為 ，但是在調用樹的同一級別上沒有兩個調用處理原始列表的相同部分;因此，每個級別的調用總共只需要O(n)個時間(每個調用都有一些固定的開銷，但是由于每個級別上只有O(n)個調用，所以這被包含在O(n)因子中)。結果是，該算法只使用c(n log n)的時間。故時間復雜度為O(n log n)。
要對n個不同元素的數組進行排序，快速排序需要O(n log n)的預期時間，推導很枯燥就不羅嗦了。
圖片來自wikipedia:
注：快排不需要額外的緩沖區開銷，但是需要棧開銷，其空間復雜度為O(log n).
這里對上表其中幾個效率相對較高的做個簡要介紹，后面如有機會再深入學習總結：
Introsort內省排序，在C++ STL中有應用。內省排序（英語：Introsort）是由David Musser在1997年設計的排序算法。這個排序算法首先從快速排序開始，當遞歸深度超過一定深度（深度為排序元素數量的對數值）后轉為堆排序。采用這個方法，內省排序既能在常規數據集上實現快速排序的高性能，又能在最壞情況下仍保持O(n log n) 的時間復雜度。由于這兩種算法都屬于比較排序算法，所以內省排序也是一個比較排序算法。
Timsort排序算法：是一種混合穩定排序算法，它是從合并排序和插入排序中派生而來的，旨在對多種實際數據表現良好。由Tim Peters在2002年實現，用于Python編程語言。該算法查找已排序（運行）的數據的子序列，并使用它們對其余部分進行更有效的排序。這是通過合并運行直到滿足特定條件來完成的。自2.3版以來，Timsort一直是Python的標準排序算法。還應用在Android平臺上的Java SE 7、GNU Octave（是一個開源的類MATLAB數序軟件）、V8（開源Java script引擎）以及Swift中，用于對非原始類型的數組進行排序。
MergeSort歸并排序：在計算機科學中，是一種高效的，通用的，基于比較的排序算法。大多數實現產生穩定的排序，這意味著相等元素的順序在輸入和輸出中是相同的。歸并排序是約翰·馮·諾伊曼（John von Neumann）在1945年發明的分而治之算法。早在1948年，Goldstine和von Neumann的報告就對自下而上的合并排序進行了詳細描述和分析。
Tournament sort：通過使用優先級隊列來查找排序中的下一個元素，它改進了選擇排序。在原始的選擇排序中，需要O（n）個操作才能選擇n個元素中的下一個元素；在錦標賽排序中，需要進行O（log n）運算（在O（n）中建立初始錦標賽之后）。錦標賽排序是堆排序的一種變體。
樹形選擇排序又稱錦標賽排序（Tournament Sort）：是一種按照錦標賽的思想進行選擇排序的方法。首先對n個記錄的關鍵字進行兩兩比較，然后在 個較小者之間再進行兩兩比較，如此重復，直至選出最小的記錄為止。
塊排序或塊合并排序Block sort: 它將至少兩個合并操作與插入排序組合在一起，以達到O(n log n)的位置穩定排序。合并兩個排序的列表，A和B，等價于將A分成大小相等的塊，在特殊規則下將每個塊插入到B中，并合并AB對。
平滑排序smoothsort，是一種基于比較的排序算法。它是堆排序的一種變體，由Edsger Dijkstra于1981年發明并發布。它的時間復雜度上限是O(n log n)，但它不是一個穩定的排序。平滑排序的優點是，如果輸入已經排序到一定程度，那么它會更接近O(n)的時間，而堆排序的平均值是O(n log n)，而不管初始排序狀態如何。
希爾排序Shellsort，也稱為Shell排序或Shell的方法，是一種就地比較排序。它可以被看作是交換排序(冒泡排序)或插入排序(插入排序)的泛化。該方法首先對彼此相距很遠的元素對進行排序，然后逐步縮小要比較的元素之間的差距。通過從相隔很遠的元素開始，它可以比簡單的最近鄰交換更快地將一些位置錯誤的元素移動到正確的位置。Donald Shell在1959年出版了第一個版本。Shellsort的運行時間很大程度上依賴于它使用的間隙序列。
說到排序算法復雜度，請一定要與應用場景結合。主要需要考慮待排數據的集的尺寸，如果數據量小的時候反而是插入排序算法應用最為廣泛；而對于海量數據場合，則應使用漸近有效排序策略。這是什么意思呢？說白了就是常使用混合算法！主要策略是利用快速排序、堆排序或歸并排序將整體快速分治排序，同時對遞歸底部的小列表采用插入排序。事實上，在實際應用中有更復雜的變體，例如在Android，Java和Python中使用的Timsort（合并排序，插入排序和其他邏輯），以及在某些C++中用的introsort（快速排序和堆排序） 在.NET中排序實現。
再說白一點，在海量數據場景，利用快速排序、堆排序或歸并排序將海量數據快速迭代成收斂的小塊，而在小塊中采用最為常見的插入排序盡快完成小塊排序，小塊中采用插入排序則可以更大程度減少遞歸深度。
在信息時代，有海量信息需要處理，即便有非常強勁的處理器，但如沒有很好的算法，仍然無法滿足對這些信息的處理。在處理過程中，免不了要進行信息進行排序，快排在時空兩個維度的開銷都比較均衡，大量的應用軟件、開發工具以及軟件包都基于快排做了大量的應用。所以說快速排序改變世界，個人認為并不為過。同時對于求職面試，快速排序算法也是高頻面試主題，值得深入研究掌握。
從0學ARM專輯匯總
0. 到底什么是Cortex、ARMv8、arm架構、ARM指令集、soc？一文幫你梳理基礎概念【科普】
1. 從0開始學ARM-安裝Keil MDK uVision集成開發環境
2. 從0開始學ARM-CPU原理，基于ARM的SOC講解
3. 從0開始學ARM-ARM模式、寄存器、流水線
推薦閱讀
進群，請加一口君微信，帶你嵌入式入門進階。
點擊“閱讀原文”查看更多分享，歡迎點分享、收藏、點贊、在看。
