PHP是一种常用的服务器端脚本语言,广泛应用于Web开发领域。在PHP中,快速排序是一种常见的排序算法,它通过分治的思想将一个大问题拆分成若干个小问题,并通过递归的方式解决这些小问题,最终将问题解决。本文将介绍几种常见的PHP快速排序代码。
1. 递归实现快速排序
function quickSort($arr) { $length = count($arr); if ($length <= 1) { return $arr; } $pivot = $arr[0]; $left = $right = array(); for ($i = 1; $i < $length; $i++) { if ($arr[$i] < $pivot) { $left[] = $arr[$i]; } else { $right[] = $arr[$i]; } } return array_merge(quickSort($left), array($pivot), quickSort($right)); } // 使用示例 $arr = array(5, 2, 8, 9, 1, 3); $result = quickSort($arr); print_r($result);
上述代码中,我们首先判断数组长度是否小于等于1,如果是,则直接返回该数组。然后选取数组的第一个元素作为基准值(pivot),将比基准值小的元素放入$left数组中,将比基准值大的元素放入$right数组中。最后,通过递归调用quickSort函数对$left和$right数组进行排序,并将结果与基准值合并返回。
2. 原地排序实现快速排序
function quickSort(&$arr, $left, $right) { if ($left >= $right) { return; } $pivot = $arr[$left]; $i = $left; $j = $right; while ($i < $j) { while ($i < $j && $arr[$j] >= $pivot) { $j--; } $arr[$i] = $arr[$j]; while ($i < $j && $arr[$i] <= $pivot) { $i++; } $arr[$j] = $arr[$i]; } $arr[$i] = $pivot; quickSort($arr, $left, $i - 1); quickSort($arr, $i + 1, $right); } // 使用示例 $arr = array(5, 2, 8, 9, 1, 3); $length = count($arr); quickSort($arr, 0, $length - 1); print_r($arr);
上述代码中,我们使用两个指针$i和$j分别从数组的左边和右边进行扫描,如果$arr[$j]小于基准值,则将$arr[$j]赋值给$arr[$i];如果$arr[$i]大于基准值,则将$arr[$i]赋值给$arr[$j]。当$i和$j相遇时,将基准值赋值给$arr[$i]。然后,通过递归调用quickSort函数对基准值左边和右边的子数组进行排序。
3. 非递归实现快速排序
function quickSort($arr) { $stack = array(array(0, count($arr) - 1)); while (!empty($stack)) { $range = array_pop($stack); $left = $range[0]; $right = $range[1]; if ($left >= $right) { continue; } $pivot = $arr[$left]; $i = $left; $j = $right; while ($i < $j) { while ($i < $j && $arr[$j] >= $pivot) { $j--; } $arr[$i] = $arr[$j]; while ($i < $j && $arr[$i] <= $pivot) { $i++; } $arr[$j] = $arr[$i]; } $arr[$i] = $pivot; $stack[] = array($left, $i - 1); $stack[] = array($i + 1, $right); } return $arr; } // 使用示例 $arr = array(5, 2, 8, 9, 1, 3); $result = quickSort($arr); print_r($result);
上述代码中,我们使用一个栈来保存待处理子数组的范围,初始时将整个数组的范围压入栈中。然后,循环处理栈中的元素,取出范围,进行与上述原地排序相同的操作,并将左右子数组的范围压入栈中。最终,栈为空时,排序完成。
以上是几种常见的PHP快速排序代码。快速排序是一种高效的排序算法,适用于大规模数据的排序。使用递归、原地排序或非递归的方式实现快速排序,可以根据实际需求选择合适的方式。希望本文能帮助到你理解和使用PHP快速排序算法。
如对本文有疑问,请提交到交流论坛,广大热心网友会为你解答!! 点击进入论坛