您现在的位置: 365建站网 > 365文章 > php 几种常见的快速排序代码

php 几种常见的快速排序代码

文章来源:365jz.com     点击数:204    更新时间:2023-04-16 03:16   参与评论

php 几种常见的快速排序代码

PHP是一种常用的服务器端脚本语言,广泛应用于Web开发领域。在PHP中,快速排序是一种常见的排序算法,它通过分治的思想将一个大问题拆分成若干个小问题,并通过递归的方式解决这些小问题,最终将问题解决。本文将介绍几种常见的PHP快速排序代码。

1. 递归实现快速排序

phpcode

  1. function quickSort($arr) {
  2. $length = count($arr);
  3. if ($length <= 1) {
  4. return $arr;
  5. }
  6. $pivot = $arr[0];
  7. $left = $right = array();
  8. for ($i = 1; $i < $length; $i++) {
  9. if ($arr[$i] < $pivot) {
  10. $left[] = $arr[$i];
  11. } else {
  12. $right[] = $arr[$i];
  13. }
  14. }
  15. return array_merge(quickSort($left), array($pivot), quickSort($right));
  16. }
  17. // 使用示例
  18. $arr = array(5, 2, 8, 9, 1, 3);
  19. $result = quickSort($arr);
  20. print_r($result);

上述代码中,我们首先判断数组长度是否小于等于1,如果是,则直接返回该数组。然后选取数组的第一个元素作为基准值(pivot),将比基准值小的元素放入$left数组中,将比基准值大的元素放入$right数组中。最后,通过递归调用quickSort函数对$left和$right数组进行排序,并将结果与基准值合并返回。

2. 原地排序实现快速排序

phpcode

  1. function quickSort(&$arr, $left, $right) {
  2. if ($left >= $right) {
  3. return;
  4. }
  5. $pivot = $arr[$left];
  6. $i = $left;
  7. $j = $right;
  8. while ($i < $j) {
  9. while ($i < $j && $arr[$j] >= $pivot) {
  10. $j--;
  11. }
  12. $arr[$i] = $arr[$j];
  13. while ($i < $j && $arr[$i] <= $pivot) {
  14. $i++;
  15. }
  16. $arr[$j] = $arr[$i];
  17. }
  18. $arr[$i] = $pivot;
  19. quickSort($arr, $left, $i - 1);
  20. quickSort($arr, $i + 1, $right);
  21. }
  22. // 使用示例
  23. $arr = array(5, 2, 8, 9, 1, 3);
  24. $length = count($arr);
  25. quickSort($arr, 0, $length - 1);
  26. print_r($arr);

上述代码中,我们使用两个指针$i和$j分别从数组的左边和右边进行扫描,如果$arr[$j]小于基准值,则将$arr[$j]赋值给$arr[$i];如果$arr[$i]大于基准值,则将$arr[$i]赋值给$arr[$j]。当$i和$j相遇时,将基准值赋值给$arr[$i]。然后,通过递归调用quickSort函数对基准值左边和右边的子数组进行排序。

3. 非递归实现快速排序

phpcode

  1. function quickSort($arr) {
  2. $stack = array(array(0, count($arr) - 1));
  3. while (!empty($stack)) {
  4. $range = array_pop($stack);
  5. $left = $range[0];
  6. $right = $range[1];
  7. if ($left >= $right) {
  8. continue;
  9. }
  10. $pivot = $arr[$left];
  11. $i = $left;
  12. $j = $right;
  13. while ($i < $j) {
  14. while ($i < $j && $arr[$j] >= $pivot) {
  15. $j--;
  16. }
  17. $arr[$i] = $arr[$j];
  18. while ($i < $j && $arr[$i] <= $pivot) {
  19. $i++;
  20. }
  21. $arr[$j] = $arr[$i];
  22. }
  23. $arr[$i] = $pivot;
  24. $stack[] = array($left, $i - 1);
  25. $stack[] = array($i + 1, $right);
  26. }
  27. return $arr;
  28. }
  29. // 使用示例
  30. $arr = array(5, 2, 8, 9, 1, 3);
  31. $result = quickSort($arr);
  32. print_r($result);

上述代码中,我们使用一个栈来保存待处理子数组的范围,初始时将整个数组的范围压入栈中。然后,循环处理栈中的元素,取出范围,进行与上述原地排序相同的操作,并将左右子数组的范围压入栈中。最终,栈为空时,排序完成。

以上是几种常见的PHP快速排序代码。快速排序是一种高效的排序算法,适用于大规模数据的排序。使用递归、原地排序或非递归的方式实现快速排序,可以根据实际需求选择合适的方式。希望本文能帮助到你理解和使用PHP快速排序算法。

如对本文有疑问,请提交到交流论坛,广大热心网友会为你解答!! 点击进入论坛

发表评论 (204人查看0条评论)
请自觉遵守互联网相关的政策法规,严禁发布色情、暴力、反动的言论。
昵称:
最新评论
------分隔线----------------------------

快速入口

· 365软件
· 杰创官网
· 建站工具
· 网站大全

其它栏目

· 建站教程
· 365学习

业务咨询

· 技术支持
· 服务时间:9:00-18:00
365建站网二维码

Powered by 365建站网 RSS地图 HTML地图

copyright © 2013-2024 版权所有 鄂ICP备17013400号