插入排序（Insertion Sort）C代码实现异常排查求助

Hey there! Let's figure out why your insertion sort code isn't doing anything—this is a super common gotcha when translating Introduction to Algorithms' pseudocode to C, since the book uses 1-based array indexing but C uses 0-based. Let's break this down.

First, Let's Recap the Book's Pseudocode #

The standard insertion sort pseudocode from Cormen et al. looks like this (1-based index):

for j = 2 to A.length
    key = A[j]
    // Insert A[j] into the sorted sequence A[1..j-1]
    i = j - 1
    while i > 0 and A[i] > key
        A[i+1] = A[i]
        i = i - 1
    A[i+1] = key

The Most Likely Bugs in Your Code #

Since your input arrays are coming out unchanged, here are the two biggest culprits:

1. Mismatched Array Indexing (1-based vs 0-based) #

If you directly copied the pseudocode's j = 2 start to C, you're skipping the first two elements (since C starts at 0). For an array like {4,3,2,1}, your loop would only touch elements at index 2 and 3—leaving the first two untouched, and never actually sorting anything meaningful.

2. Incorrect While Loop Condition #

The pseudocode uses i > 0 to stop at the first element (index 1 in the book), but in C you need i >= 0 to reach the actual first element (index 0). If you kept i > 0, your code will never compare or move the element at index 0, so small values can't bubble to the front.

Fixed Insertion Sort Code #

Here's the corrected C version that aligns with the pseudocode (adjusted for 0-based indexing):

#include <stdio.h>

void insertionSort(int arr[], int n) {
    int j, key, i;
    // Start from the SECOND element (index 1), matching pseudocode's j=2
    for (j = 1; j < n; j++) {
        key = arr[j];
        i = j - 1;
        
        // Keep moving backwards until we find the right spot for key
        // i >= 0 ensures we don't go out of bounds
        while (i >= 0 && arr[i] > key) {
            arr[i + 1] = arr[i];
            i--;
        }
        // Insert key into its correct position
        arr[i + 1] = key;
    }
}

// Helper function to print arrays
void printArray(int arr[], int size) {
    for (int i = 0; i < size; i++) {
        printf("%d ", arr[i]);
    }
    printf("\n");
}

int main() {
    int test1[] = {4, 3, 2, 1};
    int size1 = sizeof(test1) / sizeof(test1[0]);
    printf("Input {4, 3, 2, 1} → Sorted output: ");
    insertionSort(test1, size1);
    printArray(test1, size1);

    int test2[] = {8, 9, 1, 12, 3};
    int size2 = sizeof(test2) / sizeof(test2[0]);
    printf("Input {8, 9, 1, 12, 3} → Sorted output: ");
    insertionSort(test2, size2);
    printArray(test2, size2);

    return 0;
}

What Changed? #

• Loop Start: j starts at 1 instead of 2, so we process every element from the second one onward.
• While Condition: i >= 0 replaces i > 0, allowing us to compare all the way to the first element of the array.
• Core Logic: The rest stays true to the book's pseudocode—we save the current element, shift larger elements right, then insert the saved element in the correct spot.

Quick Debug Tips for Next Time #

• Add printf statements inside the loops to print the array state at each step—this lets you see exactly where the code stops working.
• Always double-check index conversions when moving between pseudocode (1-based) and C (0-based).
• Verify your loop boundaries: make sure your for loop runs for every element that needs sorting, and your while loop doesn't stop too early.

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