function swap(array &$arr,$a,$b){ $temp = $arr[$a]; $arr[$a] = $arr[$b]; $arr[$b] = $temp; } function Partition(array &$arr,$low,$high){ $pivot = $arr[$low]; //选取子数组第一个元素作为枢轴 while($low < $high){ //从数组的两端交替向中间扫描 while($low < $high && $arr[$high] >= $pivot){ $high --; } swap($arr,$low,$high); //终于遇到一个比$pivot小的数，将其放到数组低端 while($low < $high && $arr[$low] <= $pivot){ $low ++; } swap($arr,$low,$high); //终于遇到一个比$pivot大的数，将其放到数组高端 } return $low; //返回high也行，毕竟最后low和high都是停留在pivot下标处 } function QSort(array &$arr,$low,$high){ if($low < $high){ $pivot = Partition($arr,$low,$high); //将$arr[$low...$high]一分为二，算出枢轴值 QSort($arr,$low,$pivot - 1); //对低子表进行递归排序 QSort($arr,$pivot + 1,$high); //对高子表进行递归排序 } } function QuickSort(array &$arr){ $low = 0; $high = count($arr) - 1; QSort($arr,$low,$high); }
我们调用算法：
$arr = array(9,1,5,8,3,7,4,6,2); QuickSort($arr); var_dump($arr);
运行结果：
array(9) { [0]=> int(1) [1]=> int(2) [2]=> int(3) [3]=> int(4) [4]=> int(5) [5]=> int(6) [6]=> int(7) [7]=> int(8) [8]=> int(9) }
复杂度分析：
在最优的情况下，也就是选择数轴处于整个数组的中间值的话，则每一次就会不断将数组平分为两半。因此最优情况下的时间复杂度是 O(nlogn) （跟堆排序、归并排序一样）。
最坏的情况下，待排序的序列是正序或逆序的，那么在选择枢轴的时候只能选到边缘数据，每次划分得到的比上一次划分少一个记录，另一个划分为空，这样的情况的最终时间复杂度为 O(n^2).
综合最优与最差情况，平均的时间复杂度是 O(nlogn).
快速排序是一种不稳定排序方法。
由于快速排序是个比较高级的排序，而且被列为20世纪十大算法之一。。。。如此牛掰的算法，我们还有什么理由不去学他呢！
尽管这个算法已经很牛掰了，但是上面的算法程序依然有改进的地方，下面具体讨论一下
快速排序算法优化
优化一：优化选取枢轴：
在前面的复杂度分析的过程中，我们看到最坏的情况无非就是当我们选中的枢轴是整个序列的边缘值。比如这么一个序列：
9 1 5 8 3 7 4 6 2
按照习惯我们选择数组的第一个元素作为枢轴，则 $pivot = 9，在一次循环下来后划分为{1，5，8，3，7，4，6，2} 和{ }（空序列），也就是每一次划分只得到少一个记录的子序列，而另一个子序列为空。最终时间复杂度为 O(n^2)。最优的情况是当我们选中的枢轴是整个序列的中间值。但是我们不能每次都去遍历数组拿到最优值吧？那么就有了一下解决方法：
1、随机选取：随机选取 $low 到 $high 之间的数值，但是这样的做法有些撞大运的感觉了，万一没撞成功呢，那上面的问题还是没有解决。
2、三数取中法：取三个关键字先进行排序，取出中间数作为枢轴。这三个数一般取最左端、最右端和中间三个数，也可以随机取三个数。这样的取法得到的枢轴为中间数的可能性就大大提高了。由于整个序列是无序的，随机选择三个数和从左中右端取出三个数其实就是同一回事。而且随机数生成器本身还会带来时间的开销，因此随机生成不予考虑。
出于这个想法，我们修改 Partition() 函数：
function Partition(array &$arr,$low,$high){ $mid = floor($low + ($high - $low) / 2); //计算数组中间的元素的下标 if($arr[$low] > $arr[$high]){ swap($arr,$low,$high); } if($arr[$mid] > $arr[$high]){ swap($arr,$mid,$high); } if($arr[$low] < $arr[$mid]){ swap($arr,$low,$mid); } //经过上面三步之后，$arr[$low]已经成为整个序列左中右端三个关键字的中间值 $pivot = $arr[$low]; while($low < $high){ //从数组的两端交替向中间扫描（当 $low 和 $high 碰头时结束循环） while($low < $high && $arr[$high] >= $pivot){ $high --; } swap($arr,$low,$high); //终于遇到一个比$pivot小的数，将其放到数组低端 while($low < $high && $arr[$low] <= $pivot){ $low ++; } swap($arr,$low,$high); //终于遇到一个比$pivot大的数，将其放到数组高端 } return $low; //返回high也行，毕竟最后low和high都是停留在pivot下标处 }
三数取中法对于小数组有很大可能能沟得出比较理想的 $pivot，但是对于大数组就未必了，因此还有个办法是九数取中法。。。。。。
优化二：优化不必要的交换：
现在假如有个待排序的序列如下：
5 1 9 3 7 4 8 6 2
根据三数取中法我们取 5 7 2 中的 5 作为枢轴。