算法 – Perl中的QuickSort

发布时间：2020-12-16 06:09:04 所属栏目：大数据来源：网络整理

导读：我尝试在Perl中实现QuickSort,就像我在 Python和Ruby中使用以下代码一样： use strict;use warnings;sub sort { my ($lista,$p,$r) = @_; if ($p $r) { my $q = partition(@$lista,$r); sort(@$lista,$q - 1); sort(@$lista,$q + 1,$r); }}sub partition

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

use strict;
use warnings;

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

sub partition {
    my ($lista,$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,$#lista);
print @lista

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

注意：
如果我尝试执行：

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

执行结束,结果正确.

在此先感谢您的帮助.

解决方法

这是您的代码的新版本,在分区中使用了更正的算法,为了可读性而扩展了变量名称,并增加了Perl习语的使用：

use strict;
use warnings;

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

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

sub partition {
    my ($array,$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,8);
qsort @array;
print "@arrayn"; # 1 2 3 4 5 7 8 9

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

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

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

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

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

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!