在 PHP 中快速排序

Question

我尝试在PHP中实现“C”的传统Quicksort方法。它应该工作的方式在 PHP 中不起作用。此逻辑在 C 中有效，但在 PHP.

中无效

首先处理分区部分
用 $upper
递归使用快速排序函数


<?php
$array=array(7, 6, 5, 9, 2, 1, 15, 7);
$L=0;
$U=count($array)-1;
function Partition($a, $lower, $Upper)
{   
        $i=$lower;
        $j=$Upper;
        $pivot=$a[lower];

        while($i<$j)
        {

        while($a[$i]<$pivot)
        {
            $i++;
        }

        while($a[$j]>$pivot)
        {
            $j--;
        }

        if($i<$j)
        {
            $temp = $a[$i];
            $a[$i] = $a[$j];
            $a[$j] = $temp;
        }
        $i++;
        }
        $a[$lower]=$a[$j];
        $a[$j]=$pivot;

        return $j;
}
function QuickSort($a, $lower, $Upper)
{
    if($lower<$Upper)
    {
        $loc= Partition($a, $lower, $Upper);
        QuickSort($a, $lower, $loc-1);
        QuickSort($a, $loc+1, $Upper);
    }
    print_r($a);
}
QuickSort($array, $L, $U);
print_r($array);

Answer 1

在 PHP 中默认不通过引用传递数组。（它们不像在 C 中那样只是指针。）所以你的函数实际上并没有改变输入数组。

我已经在下面修改了你的函数声明，它现在可以正常工作了。

此外，您需要 $pivot=$a[lower] 才能 $pivot=$a[$lower];;

<?php
$array=array(7, 6, 5, 9, 2, 1, 15, 7);
$L=0;
$U=count($array)-1;
function Partition(&$a, $lower, $Upper)
{   
        $i=$lower;
        $j=$Upper;
        $pivot=$a[$lower];

        while($i<$j)
        {

        while($a[$i]<$pivot)
        {
            $i++;
        }

        while($a[$j]>$pivot)
        {
            $j--;
        }

        if($i<$j)
        {
            $temp = $a[$i];
            $a[$i] = $a[$j];
            $a[$j] = $temp;
        }
        $i++;
        }
        $a[$lower]=$a[$j];
        $a[$j]=$pivot;

        return $j;
}
function QuickSort(&$a, $lower, $Upper)
{
    if($lower<$Upper)
    {
        $loc= Partition($a, $lower, $Upper);
        QuickSort($a, $lower, $loc-1);
        QuickSort($a, $loc+1, $Upper);
    }
    print_r($a);
}
QuickSort($array, $L, $U);
print_r($array);

值得注意的是，PHP 提供的数组排序函数已经使用了 QuickSort 的实现。

在 PHP 中快速排序

Quick Sort in PHP

php

sorting

algorithm

quicksort