algorithm - Perl 中的快速排序

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 函数)然后调用三个参数 _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