Raku 中的快速排序
— 焉知非鱼今天,我们来看看另一个,也许是最着名的数据排序方法,快速排序。
该算法要求您选择所谓的枢轴,其中一个元素来自数据,并将其余部分分成两部分:小于枢轴的元素,以及大于或等于枢轴的元素。然后再次递归地对每个部分进行排序。在每次迭代中,部件变得越来越小,直到子列表是一个或甚至零个元素的平凡数据集。
一个单独的理论是如何选择正确的枢轴。有几种方法,例如,从列表中间取值,或取第一项,或最后一项,或随机项。还有更复杂的方法,您可以调整它以在您的数据集类型上实现最佳性能。
为简单起见,让我们选择第一个元素作为轴点,这是代码
sub quick-sort(@data) {
return @data if @data.elems <= 1;
my $pivot = @data[0];
my @left;
my @right;
for @data[1..*] -> $x {
if $x < $pivot {
push @left, $x;
}
else {
push @right, $x;
}
}
return flat(quick-sort(@left), $pivot, quick-sort(@right));
}
my @data = 4, 5, 7, 1, 46, 78, 2, 2, 1, 9, 10;
@data = quick-sort @data;
say @data;
与之前的冒泡排序示例不同,此程序不会就地排序,而是返回新列表。
现在是时候将代码转换为更具 Raku 风格代码的时候了。
Multi-subs 再次来救援,在增加代码行数的同时,使整个算法在第一眼更容易捕捉到:
multi sub quick-sort(@data where @data.elems <= 1) {
return @data;
}
multi sub quick-sort(@data where @data.elems > 1) {
my $pivot = @data[0];
. . .
}
现在,看看这两部分:
my $pivot = @data[0];
. . .
for @data[1..*] -> $x {
需要采用第一个元素,算法的其余部分仅处理列表的其余部分。目前,这是通过获取元素和切片来实现的,但是有一种切换方法可以完全满足我们的需要,并从数据中删除元素。所以,让我们使用它
my $pivot = @data.shift;
. . .
for @data -> $x {
接下来是 if-else
选择,可以有效地(尽管可能效率稍差)用两个 grep
替换:一个选择枢轴之前的部分,另一个选择其余部分。
my @left = @data.grep(* < $pivot);
my @right = @data.grep(* >= $pivot);
基本上就是这样。你还可以做的是摆脱临时变量并将过滤器放到 return
语句中
return flat(
quick-sort(@data.grep(* < $pivot)),
$pivot,
quick-sort(@data.grep(* >= $pivot))
);
这一切都在最后一次改变之前发挥作用,但现在已经 broken 了:
$ raku quick-sort.pl
Cannot call 'pop' on an immutable 'List'
in sub quick-sort at 3.pl line 6
in sub quick-sort at 3.pl line 8
in block <unit> at 3.pl line 12
问题是你需要返回一个数字列表,但每个快速排序子类都返回它自己的列表。
您可以通过在函数参数之前放置*来啜饮元素来轻松解决问题
multi sub quick-sort(*@data where @data.elems > 1) {
. . .
最终代码如下所示:
multi sub quick-sort(*@data where @data.elems <= 1) {
return @data;
}
multi sub quick-sort(*@data where @data.elems > 1) {
my $pivot = @data.shift;
return flat(
quick-sort(@data.grep(* < $pivot)),
$pivot,
quick-sort(@data.grep(* >= $pivot))
);
}
您也可以使用 |
来独立平展每个列表,而不是使用 flat
例程:
return
|quick-sort(@data.grep(* < $pivot)),
$pivot,
|quick-sort(@data.grep(* >= $pivot));
但我认为有两个可理解的中间变量以避免标点符号噪音仍然更好:
multi sub quick-sort(@data where @data.elems <= 1) {
return @data;
}
multi sub quick-sort(@data where @data.elems > 1) {
my $pivot = @data.shift;
my @left = @data.grep(* < $pivot);
my @right = @data.grep(* >= $pivot);
return flat(quick-sort(@left), $pivot, quick-sort(@right));
}
my @data = 4, 5, 7, 1, 46, 78, 2, 2, 1, 9, 10;
@data = quick-sort @data;
say @data;
作为家庭作业,创建快速排序算法的实现,该算法可就地对数据进行排序。
该代码可在 GitHub 上获得,欢迎您加入此旅程!
原文:https://raku.online/2019/06/23/101-quick-sort-in-perl-6/