INSERTION-SORT C语言实现排序结果异常，求助问题排查

原《算法导论》中的INSERTION-SORT算法（1-based索引） #

INSERTION-SORT(A)
1 for j <- 2 to length[A]
2   do key <-A[j]
3     Insert A[j] into the sorted sequence A[1..j — 1].
4     i <- j — 1
5     while i > 0 and A[i] > key
6       do A[i + 1] <- A[i]
7           i <- i — 1
8     A[i + 1] <- key

你的C语言实现代码 #

#include <stdlib.h>
#include <stdio.h>

#define MAXSIZE 6
void sorting(int (*A)[MAXSIZE]){
    int key;
    int i;
    size_t size = sizeof(*A)/sizeof((*A)[0]);
    for (int j = 1; j < size; j++){
        key = (*A)[j];
        i = j-1;
        do {
            (*A)[i+1] = (*A)[i];
            i--;
        }while(i > 0 && (*A)[i] > key);
        (*A)[i+1] = key;
    }
    for(int k = 0; k < size; k++){
        printf("\n%d", (*A)[k]);
    }
}

int main(void){
    int B[MAXSIZE] = {5, 2, 4, 6, 1, 3};
    int result;
    sorting(&B);
    return 0;
}

错误原因及修正方案 #

你的实现存在两个核心问题：

• 循环逻辑错误：原算法用while先判断条件再执行移动操作，但你改成了do-while，这会导致无论条件是否满足，都先执行一次元素移动。比如当i=0时，会先把A[0]移到A[1]，再判断条件，直接破坏了已排序的序列。
• 索引边界错误：C语言数组是0-based索引，原算法的i>0对应到0-based应该是i>=0，否则会漏掉和索引0位置元素的比较，导致最小元素无法被放到正确位置。

修正后的代码 #

#include <stdlib.h>
#include <stdio.h>

#define MAXSIZE 6
void sorting(int (*A)[MAXSIZE]){
    int key;
    int i;
    size_t size = sizeof(*A)/sizeof((*A)[0]);
    for (int j = 1; j < size; j++){
        key = (*A)[j];
        i = j-1;
        // 替换为while循环，先判断条件再执行移动
        while(i >= 0 && (*A)[i] > key){
            (*A)[i+1] = (*A)[i];
            i--;
        }
        (*A)[i+1] = key;
    }
    for(int k = 0; k < size; k++){
        printf("%d ", (*A)[k]); // 调整输出格式，一行显示结果更直观
    }
}

int main(void){
    int B[MAXSIZE] = {5, 2, 4, 6, 1, 3};
    sorting(&B);
    return 0;
}

修正说明 #

1. 把do-while循环替换为while循环，遵循原算法先判断后执行的逻辑，避免不必要的元素移动。
2. 将循环条件中的i>0改为i>=0，确保能比较到数组的第一个元素（索引0），保证最小元素能被正确插入到序列头部。
3. 调整输出格式，让排序结果在一行显示，更易读。

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