Perl中的QuickSort

Question

我尝试在Perl中实现QuickSort,就像我在Python和Ruby中使用以下代码一样:

use strict;
use warnings;

sub sort {
    my ($lista, $p, $r) = @_;
    if ($p < $r) {
        my $q = &partition(\@$lista, $p, $r);
        &sort(\@$lista, $p, $q - 1);
        &sort(\@$lista, $q + 1, $r);
    }
}

sub partition {
    my ($lista, $p, $r) = @_;
    my $x = $$lista[$r];
    my $i = $p - 1;
    for (my $j = $p; $j < @$lista - 1; $j++) {
        if ($$lista[$j] <= $x) {
            $i++;
            ($$lista[$i], $$lista[$j]) = ($$lista[$j], $$lista[$i]);
        }
    }
    ($$lista[$i + 1], $$lista[$r]) = ($$lista[$r], $$lista[$i + 1]);
    return $i + 1;
}

my @lista = (4, 3, 9, 2, 1, 7, 5, 8);
&sort(\@lista, 0, $#lista);
print @lista

在这种情况下,执行属于无限递归,我不知道为什么因为代码看起来与Python和Ruby中的相同(来自Cormen的算法,算法简介)

注意:如果我尝试执行:

my @lista = (3, 2, 1);
&sort(\@lista, 0, $#lista);
print @lista;

执行结束,结果正确.

在此先感谢您的帮助.

Answer 1

这是您的代码的新版本,其中包含已更正的算法partition,扩展的变量名称以提高可读性,并增加了对Perl习语的使用:

use strict;
use warnings;

sub qsort (\@) {_qsort($_[0], 0, $#{$_[0]})}

sub _qsort {
    my ($array, $low, $high) = @_;
    if ($low < $high) {
        my $mid = partition($array, $low, $high);
        _qsort($array, $low,     $mid - 1);
        _qsort($array, $mid + 1, $high   );
    }
}

sub partition {
    my ($array, $low, $high) = @_;
    my $x = $$array[$high];
    my $i = $low - 1;
    for my $j ($low .. $high - 1) {
        if ($$array[$j] <= $x) {
            $i++;
            @$array[$i, $j] = @$array[$j, $i];
        }
    }
    $i++;
    @$array[$i, $high] = @$array[$high, $i];
    return $i;
}

my @array = (4, 3, 9, 2, 1, 7, 5, 8);
qsort @array;
print "@array\n"; # 1 2 3 4 5 7 8 9

因为你真的不想强迫你的调用者总是qsort(@array, 0, $#array)在qsort(@array)什么时候使用,所以上面的代码创建了一个qsort包装函数,它接受一个文字数组(比如内置shift @array函数),然后调用三个arg _qsort函数.

您的exchange实现被重写为数组切片.前导符号从更改为$,@并且列表放在[...]下标中.

最后,您的代码的主要问题是您在分区中的最终条件是错误的.在你应该使用的地方$r,你使用了$#$lista导致分区在列表中运行的程度远远超过应该使用的程序.在上面的代码中,我使用了for/foreach循环而不是C风格的for(;;){...}循环:

for (my $i = 0; $i <= 100; $i++) {...}

for my $i (0 .. 100) {...} # faster and easier to read