Raku 中的插入排序

Insertion sort in Raku

   |  1   |  171   |  焉知非鱼

今天，我们研究插入排序算法及其在 Raku 中的可能实现。算法的复杂性是 O(n2)，但它是练习 Raku 的一个很好的选择。

这个想法很简单。您可以在数组中找到最小值并将其放在第一个位置。然后从第二个位置开始扫描数据（因为第一个位置已经被最低元素占用）。然后你向右走，找到最小值并将它们放到当前位置直到你到达终点。

它类似于选择排序，但不是交换两个元素，而是插入一个（因此，移动其他元素）。让我们从简单的方法和两个嵌套循环开始：

sub insertion-sort(@data) {
    for ^@data -> $i {
        for ^$i -> $j {
            if @data[$i] < @data[$j] {
                @data.splice($j, 0, @data[$i]);
                @data.splice($i + 1, 1);
            }
        }
    }
}

my @data = 4, 5, 7, 1, 46, 78, 2, 2, 1, 9, 10;
insertion-sort @data;
say @data;

在Raku中，数组的拼接方法可以完成两个任务：用另一个元素列表替换数组的一部分，或者只是删除元素或一行中的一些元素。

在上面的代码中，使用了该方法的两个应用程序。首先，将新找到的元素插入当前位置。其次，它从之前的位置删除（数组刚刚增长，因此索引变为$ i + 1）。

由于splice方法也返回已删除的元素，我们可以将第二个调用放到正在读取元素的位置：@data [$ i]。因此，可以使用以下嵌套调用替换这两行

@data.splice($j, 0, @data.splice($i, 1))

请注意，索引现在只是$ i，因为数组尚未修改。

您应该已经熟悉了第二个可能的技巧：如果出现以下情况，请使用 if 后缀：

sub insertion-sort(@data) {
    for ^@data -> $i {
        for ^$i -> $j {
            @data.splice($j, 0, @data.splice($i, 1)) 
                if @data[$i] < @data[$j];
        }
    }
}

你可以在这一点上停下来，但我希望你还不满意。至少，两个嵌套的fors似乎是进一步思考的好领域。

不幸的是，不可能直接使用交叉运算符来获得类似^ @ data X ^ @ data的东西，因为第二个列表依赖于第一个列表，但是有一种完全不同的简化代码的方法。

最内部for循环的主要目标是找到数组中的第一个最小元素。 Raku为我们提供了第一种方法，它就是这样做的。

默认情况下，它返回元素，但我们需要它的索引。您可以通过添加：k命名参数来实现

@data.first(* >= @data[$_], :k)

裸：k相当于将参数设置为True :: k（True）或k => True。

sub insertion-sort(@data) {
    for ^@data -> $i {
        @data.splice(
            @data.first(* >= @data[$i], :k), 
            0,
            @data.splice($i, 1)
        )
    }
}

最后，让剩下的for循环成为一个postfix子句，并且你完成了一个很好的单行函数（这里显示在不同的行上分成较短的部分）：

sub insertion-sort(@data) {
    @data.splice(
        @data.first(* >= @data[$_], :k), 
        0,
        @data.splice($_, 1)
    ) for ^@data;
}

my @data = 4, 5, 7, 1, 46, 78, 2, 2, 1, 9, 10;
insertion-sort @data;
say @data;

这一切都是现在，但如果你发现可以改进的东西，请在下面的评论中告诉我们。源代码可在GitHub上获得。

原文：https://raku.online/2019/06/24/102-insertion-sort-in-perl-6/

Raku 

comments powered by Disqus