算法 – Perl中的QuickSort

概述我尝试在Perl中实现QuickSort,就像我在 Python和Ruby中使用以下代码一样： use strict;use warnings;sub sort { my ($lista, $p, $r) = @_; if ($p < $r) { my $q = &partition(\@$lista, $p, $r); &sort(\@$li 我尝试在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 "@array\n"; # 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

总结

以上是内存溢出为你收集整理的算法 – Perl中的QuickSort全部内容，希望文章能够帮你解决算法 – Perl中的QuickSort所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。