这是插入排序的有效形式吗？

Question

以下代码是否表示插入排序的有效实现？

use warnings;

@arr = (5, 2, 4, 6, 1, 3);
$size = @arr;
print "\nUnsorted array: @arr\n";

for ( $i = 1; $i < $size; $i++ ) {

    while ( $i > 0 && $arr[$i] < $arr[$i-1] ) {

        ($arr[$i], $arr[$i-1]) = ($arr[$i-1], $arr[$i]);
        $i--;
    }
}

print "Sorted Array:   @arr\n";

Answer 1

是的。它与显示的第一个算法相同 on Wikipedia

Answer 2

是的，但它不必要地重新访问已经排序的元素。固定：

for my $i (1..#$arr) {
    my $j = $i;
    while ( $j > 0 && $arr[$j] < $arr[$j-1] ) {
        ($arr[$j], $arr[$j-1]) = ($arr[$j-1], $arr[$j]);
        $j--;
    }
}

我添加了my $j = $i;，并在内部循环中从$i切换到$j。对 for 循环的更改不是功能更改；它只是更干净、更快。

现在，该算法与 Wikipedia 上显示的第一个算法相同。

基本上，将 @arr 视为两个数组。前导元素形成排序数组，尾随元素形成未排序元素数组以插入。 $i 是未排序元素的第一个元素的索引，内部循环将 $arr[$i] 插入适当的位置。

这是插入排序的有效形式吗？

Is this a valid form of insertion sort?

sorting

perl

insertion-sort