PHP排序算法之快速排序(Quick Sort)及其优化算法详解

发布时间：2021-05-23 14:24:17 所属栏目：PHP教程来源：网络整理

导读：本篇章节讲解PHP排序算法之快速排序(Quick Sort)及其优化算法。供大家参考研究具体如下：基本思想：快速排序（Quicksort）是对冒泡排序的一种改进。他的基本思想是：通过一趟排序将待排记录分割成独立的两部分，其中一部分的关键字均比另一部分

出于这个想法，我们修改 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 比较合适，实际情况可以是适当调整），就用直接插入排序，这样就能保证最大化的利用这两种排序的优势来完成排序工作。

优化四：优化递归操作：

大家知道，递归对性能时有一定影响的，QSort()函数在其尾部有两次递归的操作，如果待排序的序列划分极端不平衡（就是我们在选择枢轴的时候不是中间值），那么递归的深度将趋近于 n，而不是平衡时的 log₂n，这就不仅仅是速度快慢的问题了。

我们也知道，递归是通过栈来实现的，栈的大小是很有限的，每次递归调用都会耗费一定的栈空间，函数的参数越多，每次递归耗费的空间也越多，因此如果能减少队规，将会大大提高性能。

听说，递归都可以改造成循环实现。我们在这里就是使用循环去优化递归。（关于递归与循环大家可以参考知乎里面的讨论《所有递归都可以改写成循环吗？》）

我们对QSort() 函数尾部递归进行优化：

= $high 时表示不能再进行分组，已经能够得出正确结果了 if(($high - $low) > MAX_LENGTH_INSERT_SORT){ while($low < $high){ $pivot = Partition($arr,$high); //将$arr[$low...$high]一分为二，算出枢轴值 QSort($arr,$pivot - 1); //对低子表（$pivot左边的记录）进行递归排序 $low = $pivot + 1; } }else{ //直接插入排序 InsertSort($arr); } }

在上面，我们使用循环替换递归，减少了之前一般的递归量。结果是一样的，但是采用循环而不是递归的方法可以缩减堆栈的深度，从而提高了整体性能。

好了、终于写完了。这篇博客基本上是 Copy 《》里面的内容，在这里总结出来不仅是一个记录，大家也可以从中获得很大的收获。

PS：这里再为大家推荐一款关于排序的演示工具供大家参考：

在线动画演示插入/选择/冒泡/归并/希尔/快速排序算法过程工具：

更多关于PHP相关内容感兴趣的读者可查看本站专题：《》、《》、《》、《》、《》、《》及《》

希望本文所述对大家PHP程序设计有所帮助。

（编辑：威海站长网）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!

3/3

首页

PHP实例 PHP取GB2312编	用PHP5的SimpleXML分析
运用PHP的OOP特性实现	PHP完成任意字符集下正