C語言排序中快速排序的技巧

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

算法步驟：

1 從數(shù)列中挑出一個元素，稱為 “基準(zhǔn)”（pivot）。

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

3 遞歸（recursive）的把小于基準(zhǔn)值元素的子數(shù)列和大于基準(zhǔn)值元素的子數(shù)列排序。

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

C代碼的實現(xiàn)如下：

下面開始單步分析，這里用一個數(shù)組的數(shù)據(jù)來分析

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

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

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

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

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

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

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

到這里可以看到數(shù)據(jù)排序已經(jīng)完成了。整體運行流程如下：

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

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

最好情況下數(shù)據(jù)也要進(jìn)行比較9次。

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

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

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

編輯：jq