PHP实现快速排序的两种常见算法

结果与目标

通过以下两种方法将无序数组转换为有序数组，并理解其背后的逻辑差异与适用场景。

准备条件

• 已配置好的 PHP 运行环境。
• 基础的 PHP 语法知识，包括变量赋值、循环结构和函数定义。

真实操作顺序

第1步：使用数组拆分与递归合并（分治法）

目的：通过选取基准值将数组分为“小”和“大”两部分，递归排序后重新组合。这种方法代码简洁，逻辑直观，但会创建大量临时数组，内存消耗相对较高。

1. 入口与判断：首先检查数组长度，若小于等于1则直接返回，作为递归终止条件。
2. 选取基准：选取数组第一个元素 $key 作为比较标准。
3. 分区操作：遍历剩余元素，比基准小的放入左数组 $left_arr，否则放入右数组 $right_arr。
4. 递归执行：对左右子数组分别调用自身函数进行排序。
5. 合并结果：使用 array_merge 将排序后的左数组、基准值、右数组合并。

<?php
function quicksort($str){
    //如果个数不大于一，直接返回
    if(count($str)<=1) return $str;
    
    //取一个值，稍后用来比较
    $key=$str[0];
    $left_arr=array();
    $right_arr=array();
    
    for($i=1;$i<count($str);$i++){
        //比$key大的放在右边，小的放在左边
        if($str[$i]<=$key)
            $left_arr[]=$str[$i];
        else
            $right_arr[]=$str[$i];
    }
    
    $left_arr=quicksort($left_arr);      //进行递归
    $right_arr=quicksort($right_arr);
    
    //将左中右的值合并成一个数组
    return array_merge($left_arr,array($key),$right_arr);
}

//测试代码
$str=array(5,3,8,2,5,9,7,2,1,4,0);
print_r(quicksort($str));
?>

第2步：使用双指针交换（原地排序法）

目的：通过在原数组中移动左右两个指针并交换不符合条件的元素，减少内存分配。这种方法空间复杂度更低，但逻辑相对复杂。

1. 初始化指针：设定左指针 $l 为 $left，右指针 $r 为 $right。
2. 选取基准：选择中间位置的元素作为枢轴 $pivot。
3. 循环扫描：当 $l < $r 时：
   • 左指针向右移，直到找到大于等于枢轴的元素。
   • 右指针向左移，直到找到小于等于枢轴的元素。
4. 元素交换：如果 $l < $r，交换 $arr[$l] 与 $arr[$r] 的值，并根据是否与枢轴相等调整指针位置以防死循环。
5. 递归区间：根据指针最终位置，对左右两个子区间继续进行快速排序。

/* @快速排序法 */
function quickSort($left, $right, &$arr){
    $l = $left;
    $r = $right;
    $pivot = $arr[(int)(($left + $right) / 2)];
    $temp = 0;
    
    while($l < $r){
        while($arr[$l] < $pivot){
            $l++;
        }
        while($arr[$r] > $pivot){
            $r--;
        }
        
        if($l >= $r) break;
        
        //交换元素
        $temp = $arr[$l];
        $arr[$l] = $arr[$r];
        $arr[$r] = $temp;
        
        //如果左边等于枢纽，左指针前移避免死循环
        if($arr[$l] == $pivot) --$r;
        //如果右边等于枢纽，右指针后移避免死循环
        if($arr[$r] == $pivot) ++$l;
    }
    
    if($l == $r){
        $l++;
        $r--;
    }
    
    //向左递归
    if($left < $r){
        quickSort($left, $r, $arr);
    }
    //向右递归
    if($right > $l){
        quickSort($l, $right, $arr);
    }
}

注意：上述第2种方法需要在调用时传入数组引用 &$arr，以实现原地修改。调用示例：quickSort(0, count($arr)-1, $arr);

完成判断

对于第一种写法，控制台或页面输出应为按升序排列的数字序列。
对于第二种写法，原数组 $arr 在函数调用后将变为有序状态。

简要总结

快速排序的核心在于“分而治之”。第一种 PHP 实现方式借助数组函数，代码可读性极高，适合初学者理解算法逻辑；第二种方式通过双指针操作实现原地排序，更符合底层算法优化的思维，在处理大规模数据时具有更好的内存性能优势。以上就是PHP实现快速排序函数的详细内容，更多关于PHP算法的资料请关注本站其它相关文章！