快速排序是由東尼·霍爾所發(fā)展的一種排序算法。在平均狀況下，排序 n 個項目要Ο(n log n)次比較。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見。事實上，快速排序通常明顯比其他Ο(n log n) 算法更快，因為它的內部循環(huán)（inner loop）可以在大部分的架構上很有效率地被實現出來。

算法步驟：

1 從數列中挑出一個元素，稱為 "基準"（pivot）。

2 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區(qū)退出之后，該基準就處于數列的中間位置。這個稱為分區(qū)（partition）操作。

3 遞歸（recursive）的把小于基準值元素的子數列和大于基準值元素的子數列排序。

遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個算法總會退出，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最后的位置去。

C代碼的實現如下：

下面開始單步分析，這里用一個數組的數據來分析

首先將0作為比較的基準，由于右邊所有的數據都比0大，所以數據不做 移動。 接下來將8作為比較基準，從最右邊開始和8比較。 此時6比8小，將6移動到8前面，其他數據依次后移。

接著在將2和8比較，2比8小，繼續(xù)將2移動到8前面，其他的數據依次后移。

這樣將8小的數據移動到8的前面，比8大的數據在8后面保持不變。移動完成后如下：

接下來比較的基準變?yōu)閿底?，將比6小的數據移動到6前面。 從最右邊開始查找，找到1比6小，將1移動到6前面。

然后繼續(xù)依次尋找比6小的數字，移動到6的前面，移動完成后如下：

然后比較的基準變?yōu)閿底?，從最右邊開始尋找比5小的數移動到5前面。查找到的數據為2。

依次查找其他比5小的數據，移動完成后如下：

到這里可以看到數據排序已經完成了。 整體運行流程如下：

下面測試一下最壞情況下的排序情況

可以看到最壞情況下排序的次數并沒有增多，反而感覺還減少了。 在看一下最好情況下的排序情況：

最好情況下數據也要進行比較9次。

下來隨機生成一個包含10000個數字的數組，測試下執(zhí)行時間。

可以看到對10000個數字排序需要的時間為120ms。

下面用一張動圖來演示一下快速排序的過程：

另外，對現在我們的大多數朋友來說還是學編程技術最重要！栽一棵樹最好的時間是十年前，其次是現在。對于準備學習編程的小伙伴，如果你想更好的提升你的編程核心能力（內功）不妨從現在開始！

微信公眾號：C語言編程學習基地

整理分享（多年學習的源碼、項目實戰(zhàn)視頻、項目筆記，基礎入門教程）

歡迎轉行和學習編程的伙伴，利用更多的資料學習成長比自己琢磨更快哦！