
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快速排序算法。
如对本文有疑问,请提交到交流论坛,广大热心网友会为你解答!! 点击进入论坛