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

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

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

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

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快速排序算法。

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

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

快速入口

· 365软件
· 建站公司
· 杰创官网
· 建站工具

业务咨询

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

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

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