perl - 这是一种有效的插入排序形式吗？

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";

标签： perlsortinginsertion-sort

Answer 1

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

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;从$ito切换。$j对 for 循环的更改不是功能更改；它只是更清洁，更快。

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

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