### 基本原理
选择一个基准元素，通常选择第一个元素或者最后一个元素。通过一趟扫描，将待排序列分成两部分，一部分比基准元素小，一部分大于等于基准元素。此时基准元素在其排好序后的正确位置，然后再用同样的方法递归地排序划分的两部分。
### 动画演示
### 算法步骤
快速排序使用分治法策略来把一个序列分为两个子序列，步骤：
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] 交换的时刻。
