快速排序是由東尼·霍爾所發(fā)展的一種排序算法镇饮。在平均狀況下取逾，排序 n 個(gè)項(xiàng)目要Ο(n log n)次比較耗绿。在最壞狀況下則需要Ο(n2)次比較，但這種狀況并不常見砾隅。事實(shí)上误阻，快速排序通常明顯比其他Ο(n log n) 算法更快，因?yàn)樗膬?nèi)部循環(huán)（inner loop）可以在大部分的架構(gòu)上很有效率地被實(shí)現(xiàn)出來。
快速排序使用分治法（Divide and conquer）策略來把一個(gè)串行（list）分為兩個(gè)子串行（sub-lists）究反。
上面部分是引用網(wǎng)上的說法寻定，我對(duì)這些定義總是記不太清楚。
我們下面直接看實(shí)現(xiàn)步驟
1 . 從數(shù)列中挑出一個(gè)元素精耐，稱為 “基準(zhǔn)”（這個(gè)基準(zhǔn)的找出方式有很多狼速，在這里我們就默認(rèn)使用第一個(gè)元素作為基準(zhǔn)）
- 重新排序數(shù)列，所有元素比基準(zhǔn)值小的擺放在基準(zhǔn)前面卦停，所有元素比基準(zhǔn)值大的擺在基準(zhǔn)的后面（相同的數(shù)可以到任一邊）向胡。在這個(gè)分區(qū)退出之后，該基準(zhǔn)就處于數(shù)列的中間位置沫浆。這個(gè)稱為分區(qū)（partition）操作捷枯。
- 從第二步中得到的基準(zhǔn)的中間位置將數(shù)組分成兩部分，遞歸地（recursive）把小于基準(zhǔn)值元素的子序列和大于基準(zhǔn)值元素的子序列排序专执。
- 重復(fù)第二步淮捆，直到子序列的數(shù)值個(gè)數(shù)為1
其中一次排序的過程可以參考下圖
上面我們了解了一趟找基準(zhǔn)位置的過程，下面我們做的只需要通過遞歸的方式按照基準(zhǔn)的位置分割數(shù)組本股，依次對(duì)子數(shù)組進(jìn)行上述過程攀痊。
下面我們看實(shí)現(xiàn)過程
function FindPv(&$arr,$s,$e){
$p = $s; //基準(zhǔn)起始位置
$v = $arr[$p]; //將數(shù)組的第一個(gè)值作為基準(zhǔn)值
while($s<$e){
while($arr[$e]>$v&&$e>$p){
$e--;
}
$arr[$p] = $arr[$e];
$p = $e;
while($arr[$s]<$v&&$s<$p){
$s++;
}
$arr[$p] = $arr[$s];
$p = $s;
}
$arr[$p] = $v;
return $p;
}
function PvSort(&$arr,$s,$e){
if($s>=$e) return ;
$nextP = FindPv($arr,$s,$e); //找到下一個(gè)基準(zhǔn)所在位置
PvSort($arr,$s,$nextP-1);
PvSort($arr,$nextP+1,$e);
}
$arr = array(10,6,8,23,4,1,17,56,32,50,11,9);
PvSort($arr);
print_r($arr);
以上是通過遞歸的方式實(shí)現(xiàn)快速排序的。遞歸拄显，使用起來非常方便苟径，可以使我們整體上把握程序的架構(gòu)。對(duì)于底層的細(xì)節(jié)躬审，系統(tǒng)已經(jīng)幫我們做了棘街，其實(shí)遞歸的底層借助的就是棧的機(jī)制。 我們自己亦可以不用遞歸承边，直接借助棧的機(jī)制實(shí)現(xiàn)上述快速排序算法遭殉，可以查看 快速排序 非遞歸實(shí)現(xiàn)。這樣將更有助于我們對(duì)算法的實(shí)現(xiàn)機(jī)制有更深的理解博助。
希望本篇對(duì)大家有所幫助险污。
