请问以下Perl代码是否为插入排序的有效实现形式？

Great question! Let's break this down clearly:

Is this a valid form of insertion sort? #

Absolutely! Insertion sort's core idea is building a sorted sequence one element at a time—for each unsorted element, you compare it with the already sorted elements before it, find its correct position, and place it there.

The approach used here—swapping the current element backward with adjacent elements until it's in the right spot—is a totally valid variant of insertion sort. The "standard" insertion sort sometimes uses a temporary variable to hold the current element, shifts larger elements forward, then inserts the temp value; but swapping adjacent elements is just a different implementation detail that follows the exact same core logic.

Is the provided Perl code a valid insertion sort implementation? #

Yes, it is! Let's walk through the code (first, fixing the HTML-escaped characters to their actual Perl syntax):

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

How it works (and why it's insertion sort): #

• The outer loop starts at index 1 (the second element), which makes sense because the first element is trivially a sorted sequence of length 1.
• The inner while loop checks if the current element is smaller than the one before it. If so, it swaps them, then moves $i backward to keep comparing with the next element in the sorted portion. This effectively "bubbles" the current element left until it lands in a position where all elements before it are smaller (or it hits the start of the array).
• When you run this code, it correctly sorts the input array (5, 2, 4, 6, 1, 3) into (1, 2, 3, 4, 5, 6).

A small readability tweak (optional): #

Your code works perfectly, but modifying the outer loop's $i variable inside the while loop can make the logic a bit harder to follow at first. A more "conventional" insertion sort implementation uses a separate variable for traversing the sorted portion, like this:

use warnings;
@arr = (5, 2, 4, 6, 1, 3);
$size = @arr;
print "\nUnsorted array: @arr\n";
for ( my $i = 1; $i < $size; $i++ ) {
    my $current_val = $arr[$i];
    my $j = $i - 1;
    # Shift elements of the sorted portion forward if they're larger than current_val
    while ( $j >= 0 && $arr[$j] > $current_val ) {
        $arr[$j+1] = $arr[$j];
        $j--;
    }
    # Insert the current value in its correct spot
    $arr[$j+1] = $current_val;
}
print "Sorted Array: @arr\n";

This does the same thing, just with a different implementation style—but your original code is still a fully valid insertion sort.

内容的提问来源于stack exchange，提问作者Leon Schulze