### 基本原理
選擇一個基準元素，通常選擇第一個元素或者最后一個元素。通過一趟掃描，將待排序列分成兩部分，一部分比基準元素小，一部分大于等于基準元素。此時基準元素在其排好序后的正確位置，然后再用同樣的方法遞歸地排序劃分的兩部分。
### 動畫演示
### 算法步驟
快速排序使用分治法策略來把一個序列分為兩個子序列，步驟：
1. 從數列中挑出一個元素，稱為"基準"。
2. 重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的后面（相同的數可以到任一邊）。在這個分區結束之后，該基準就處于數列的中間位置。這個稱為分區操作。
3. 遞歸地把小于基準值元素的子數列和大于基準值元素的子數列排序。
遞歸的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞歸下去，但是這個算法總會結束，因為在每次的迭代中，它至少會把一個元素擺到它最后的位置去。
### 代碼實現
```
// 快速排序
function quickSort($arr)
{
$length = count( $arr );
if( $length <= 1 ) return $arr;
$left = array();
$right = array();
$mid_value = $arr[0];
for ($i = 1; $i < $length; $i++) {
if ($arr[$i] < $mid_value) {
$left[] = $arr[$i];
}else{
$right[] = $arr[$i];
}
}
return array_merge(quickSort($left), (array)$mid_value, quickSort($right));
}
// 調用測試
$arr = [3,1,13,5,7,11,2,4,14,9,150,6,12,10,8];
print_r(quickSort($arr));
```
### 平均時間復雜度：O(N*logN)
在最好的情況，每次我們運行一次分區，我們會把一個數列分為兩個幾近相等的片段。這個意思就是每次遞歸調用處理一半大小的數列。因此，在到達大小為一的數列前，我們只要作log n次嵌套的調用。這個意思就是調用樹的深度是O(log n)。但是在同一層次結構的兩個程序調用中，不會處理到原來數列的相同部分；因此，程序調用的每一層次結構總共全部僅需要O(n)的時間（每個調用有某些共同的額外耗費，但是因為在每一層次結構僅僅只有O(n)個調用，這些被歸納在O(n)系數中）。結果是這個算法僅需使用O(n log n)時間。
另外一個方法是為T(n)設立一個遞歸關系式，也就是需要排序大小為n的數列所需要的時間。在最好的情況下，因為一個單獨的快速排序調用牽涉了O(n)的工作，加上對n/2大小之數列的兩個遞歸調用，這個關系式可以是：
T(n) = O(n) + 2T(n/2)
解決這種關系式類型的標準數學歸納法技巧告訴我們T(n) = O(n log n)。
事實上，并不需要把數列如此精確地分區；即使如果每個基準值將元素分開為99%在一邊和1%在另一邊，調用的深度仍然限制在100logn，所以全部運行時間依然是O(n log n)。
然而，在最壞的情況是，兩子數列擁有大各為1和n-1，且調用樹變成為一個n個嵌套調用的線性連串。第i次調用作了O(n-i)的工作量，且 ∑i = 0n(n - i) = O(n2)遞歸關系式為：
T(n) = O(n) + T(1) + T(n - 1) = O(n) + T(n - 1)
這與插入排序和選擇排序有相同的關系式，以及它被解為T(n) = O(n2)。
### 小結
快速排序有兩個方向，左邊的i下標一直往右走，當a[i] <= a[center_index]，其中center_index是中樞元素的數組下標，一般取為數組第0個元素。而右邊的j下標一直往左走，當a[j] > a[center_index]。如果i和j都走不動了，i <= j, 交換a[i]和a[j],重復上面的過程，直到i>j。 交換a[j]和a[center_index]，完成一趟快速排序。在中樞元素和a[j]交換的時候，很有可能把前面的元素的穩定性打亂，比如序列為 5 3 3 4 3 8 9 10 11， 現在中樞元素5和3(第5個元素，下標從1開始計)交換就會把元素3的穩定性打亂，所以快速排序是一個不穩定的排序算法，不穩定發生在中樞元素和a[j] 交換的時刻。
