快速排序是由東尼·霍爾所發展的一種排序演算法。在平均狀況下，排序 n 個專案要Ο（n log n）次比較。在最壞狀況下則需要Ο（n2）次比較，但這種狀況並不常見。事實上，快速排序通常明顯比其他Ο（n log n） 演算法更快，因為它的內部迴圈（inner loop）可以在大部分的架構上很有效率地被實現出來。
快速排序使用分治法（Divide and conquer）策略來把一個序列（list）分為兩個子序列（sub-lists）。
上面部分是引用網上的說法，我對這些定義總是記不太清楚。
我們下面直接看實現步驟
從數列中挑出一個元素，稱為 “基準”（這個基準的找出方式有很多，在這裡我們就預設使用第一個元素作為基準）
重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分割槽退出之後，該基準就處於數列的中間位置。這個稱為分割槽（partition）操作。
從第二步中得到的基準的中間位置將陣列分成兩部分，遞迴地（recursive）把小於基準值元素的子序列和大於基準值元素的子序列排序。
重複第二步，直到子序列的數值個數為1
其中一次排序的過程可以參考下圖
上面我們瞭解了一趟找基準位置的過程，下面我們做的只需要透過遞迴的方式按照基準的位置分割陣列，依次對子陣列進行上述過程。
下面我們看實現過程
function FindPv（&$arr，$s，$e）{ $p = $s； //基準起始位置 $v = $arr［$p］； //將陣列的第一個值作為基準值 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）； //找到下一個基準所在位置 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）；
以上是透過遞迴的方式實現快速排序的。遞迴，使用起來非常方便，可以使我們整體上把握程式的架構。對於底層的細節，系統已經幫我們做了，其實遞迴的底層藉助的就是棧的機制。 我們自己亦可以不用遞迴，直接藉助棧的機制實現上述快速排序演算法，可以檢視 快速排序 非遞迴實現。這樣將更有助於我們對演算法的實現機制有更深的理解。
希望本篇對大家有所幫助。
0人點贊
技術
