PowerShell插入排序代码异常排查：输出不符合升序预期

Based on your unexpected output (8,2,11,12,12,12,12) instead of the sorted array, here are the most likely root causes and fixes:

1. Missing Key Storage Before Shifting #

If you don't save the value of the element you're inserting (the "key") before shifting elements to the right, you'll overwrite existing values with the last element in the sorted portion. This explains the repeated 12s in your output—you're losing the original values you intended to insert and replacing them with the final element of the array.

Fix: Always store the current element as the key before entering the inner shift loop. For example:

$key = $array[$i] # Save the element to insert

2. Incorrect Inner Loop Logic #

Your output has 8 followed by 2, which means the code didn't shift 8 to the right to make space for 2. This happens if your inner loop doesn't check all elements in the sorted portion that are larger than the key, or if the loop condition is reversed (e.g., checking for elements smaller than the key instead of larger).

Fix: Ensure the inner loop runs while $j is non-negative and the element at $j is greater than the key. Decrement $j each iteration, then place the key at $j+1:

while ($j -ge 0 -and $array[$j] -gt $key) {
    $array[$j + 1] = $array[$j]
    $j--
}
$array[$j + 1] = $key

3. Wrong Loop Index Initialization #

Insertion sort starts sorting from the second element (index 1), since the first element is trivially sorted. If your outer loop starts at index 0, or your inner loop starts at an incorrect position (like the end of the array), it can break the shifting process.

Fix: Start the outer loop at index 1, and initialize the inner loop at $i-1:

for ($i = 1; $i -lt $array.Count; $i++) {
    $key = $array[$i]
    $j = $i - 1
    # ... inner loop logic ...
}

Working Example Code #

Here's a corrected PowerShell insertion sort implementation that produces your expected output:

$array = @(8, 2, 5, 6, 7, 11, 12)

for ($i = 1; $i -lt $array.Count; $i++) {
    $key = $array[$i]
    $j = $i - 1

    while ($j -ge 0 -and $array[$j] -gt $key) {
        $array[$j + 1] = $array[$j]
        $j--
    }

    $array[$j + 1] = $key
}

Write-Output $array # Outputs: 2 5 6 7 8 11 12

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