到了这一步，我们发现 $low 和 $high“碰头”了：他们都指向了下标 2。于是，第一遍比较结束。得到结果如下，凡是 $pivot(=6) 左边的数都比它小，凡是 $pivot 右边的数都比它大。
然后，对 、$pivot 两边的数据 {3，2} 和 {7，8，9}，再分组分别进行上述的过程，直到不能再分组为止。
注意：第一遍快速排序不会直接得到最终结果，只会把比k大和比k小的数分到k的两边。为了得到最后结果，需要再次对下标2两边的数组分别执行此步骤，然后再分解数组，直到数组不能再分解为止（只有一个数据），才能得到正确结果。
算法实现：
主函数中，由于第一遍快速排序是对整个数组排序的，因此开始是 $low=0,$high=count($arr)-1。
然后 QSort() 函数是个递归调用过程，因此对它封装了一下：
= $high 时表示不能再进行分组，已经能够得出正确结果了
if($low < $high){
$pivot = Partition($arr,$high); //将$arr[$low...$high]一分为二，算出枢轴值
QSort($arr,$pivot - 1); //对低子表（$pivot左边的记录）进行递归排序
QSort($arr,$pivot + 1,$high); //对高子表（$pivot右边的记录）进行递归排序
}
}
从上面的 QSort()函数中我们看出，Partition()函数才是整段代码的核心，因为该函数的功能是：选取当中的一个关键字，比如选择第一个关键字。然后想尽办法将它放到某个位置，使得它左边的值都比它小，右边的值都比它大，我们将这样的关键字成为枢轴（pivot）。
直接上代码：
= $pivot){
$high --;
}
swap($arr,$high); //终于遇到一个比$pivot小的数，将其放到数组低端
while($low < $high && $arr[$low] <= $pivot){
$low ++;
}
swap($arr,$high); //终于遇到一个比$pivot大的数，将其放到数组高端
}
return $low; //返回high也行，毕竟最后low和high都是停留在pivot下标处
}
组合起来的整个代码如下：
= $pivot){
$high --;
}
swap($arr,$high); //终于遇到一个比$pivot大的数，将其放到数组高端
}
return $low; //返回high也行，毕竟最后low和high都是停留在pivot下标处
}
function QSort(array &$arr,$high){
if($low < $high){
$pivot = Partition($arr,$pivot - 1); //对低子表进行递归排序
QSort($arr,$high); //对高子表进行递归排序
}
}
function QuickSort(array &$arr){
$low = 0;
$high = count($arr) - 1;
QSort($arr,$high);
}
我们调用算法：
运行结果：
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).
综合最优与最差情况，平均的时间复杂度是
快速排序是一种不稳定排序方法。
由于快速排序是个比较高级的排序，而且被列为20世纪十大算法之一。。。。如此牛掰的算法，我们还有什么理由不去学他呢！
尽管这个算法已经很牛掰了，但是上面的算法程序依然有改进的地方，下面具体讨论一下
快速排序算法优化
优化一：优化选取枢轴：
在前面的复杂度分析的过程中，我们看到最坏的情况无非就是当我们选中的枢轴是整个序列的边缘值。比如这么一个序列：
按照习惯我们选择数组的第一个元素作为枢轴，则 $pivot = 9，在一次循环下来后划分为{1，5，8，3，7，4，6，2} 和{ }（空序列），也就是每一次划分只得到少一个记录的子序列，而另一个子序列为空。最终时间复杂度为 O(n^2)。最优的情况是当我们选中的枢轴是整个序列的中间值。但是我们不能每次都去遍历数组拿到最优值吧？那么就有了一下解决方法：
1、随机选取：随机选取 $low 到 $high 之间的数值，但是这样的做法有些撞大运的感觉了，万一没撞成功呢，那上面的问题还是没有解决。
2、三数取中法：取三个关键字先进行排序，取出中间数作为枢轴。这三个数一般取最左端、最右端和中间三个数，也可以随机取三个数。这样的取法得到的枢轴为中间数的可能性就大大提高了。由于整个序列是无序的，随机选择三个数和从左中右端取出三个数其实就是同一回事。而且随机数生成器本身还会带来时间的开销，因此随机生成不予考虑。
出于这个想法，我们修改 Partition() 函数：
$arr[$high]){
swap($arr,$high);
}
if($arr[$mid] > $arr[$high]){
swap($arr,$mid,$high);
}
if($arr[$low] < $arr[$mid]){
swap($arr,$mid);
}
//经过上面三步之后，$arr[$low]已经成为整个序列左中右端三个关键字的中间值
$pivot = $arr[$low];
while($low < $high){ //从数组的两端交替向中间扫描（当 $low 和 $high 碰头时结束循环）
while($low < $high && $arr[$high] >= $pivot){
$high --;
}
swap($arr,$high); //终于遇到一个比$pivot大的数，将其放到数组高端
}
return $low; //返回high也行，毕竟最后low和high都是停留在pivot下标处
}
三数取中法对于小数组有很大可能能沟得出比较理想的 $pivot，但是对于大数组就未必了，因此还有个办法是九数取中法。。。。。。
优化二：优化不必要的交换：
现在假如有个待排序的序列如下：
根据三数取中法我们取 5 7 2 中的 5 作为枢轴。
当你按照快速排序算法走一个循环，你会发现 5 的下标变换顺序是这样的：0 -> 8 -> 2 -> 5 -> 4，但是它的最终目标就是 4 的位置，当中的交换其实是不需要的。
根据这个思想，我们改进我们的 Partition() 函数:
= $pivot){
$high --;
}
//swap($arr,$high); //终于遇到一个比$pivot小的数，将其放到数组低端
$arr[$low] = $arr[$high]; //使用替换而不是交换的方式进行操作
while($low < $high && $arr[$low] <= $pivot){
$low ++;
}
//swap($arr,$high); //终于遇到一个比$pivot大的数，将其放到数组高端
$arr[$high] = $arr[$low];
}
$arr[$low] = $temp; //将枢轴数值替换回 $arr[$low];
return $low; //返回high也行，毕竟最后low和high都是停留在pivot下标处
}
在上面的改进中，我们使用替换而不是交进行操作，由于在这当中少了多次的数据交换，因此在性能上也是有所提高的。
优化三：优化小数组的排序方案：
对于一个数学科学家、博士生导师，他可以攻克世界性的难题，可以培育最优秀的数学博士，当让他去教小学生“1 + 1 = 2”的算术课程，那还真未必比常年在小学里耕耘的数学老师教的好。换句话说，大材小用有时会变得反而不好用。
也就是说，快速排序对于比较大数组来说是一个很好的排序方案，但是假如数组非常小，那么快速排序算法反而不如直接插入排序来得更好（直接插入排序是简单排序中性能最好的）。其原因在于快速排序用到了递归操作，在大量数据排序的时候，这点性能影响相对于它的整体算法优势而言是可以忽略的，但如果数组只有几个记录需要排序时，这就成了大炮打蚊子的大问题。
因此我们需要修改一下我们的 QSort() 函数：
= $high 时表示不能再进行分组，已经能够得出正确结果了
if(($high - $low) > MAX_LENGTH_INSERT_SORT){
$pivot = Partition($arr,$high); //对高子表（$pivot右边的记录）进行递归排序
}else{
//直接插入排序
InsertSort($arr);
}
}
PS：上面的直接插入排序算法大家可以参考：《》
在这里我们增加一个判断，当 $high - $low 不大于一个常数时（有资料认为 7 比较合适，也有认为 50 比较合适，实际情况可以是适当调整），就用直接插入排序，这样就能保证最大化的利用这两种排序的优势来完成排序工作。
优化四：优化递归操作：
服务热线 19970861797
