C 中的插入排序未正确迭代数组

Question

我试图在 C 中实现插入排序，但它没有正确地遍历数组。我正在尝试实现 Cormen 的算法书中的伪代码。

看起来第一个元素被忽略了，但所有其他元素都被跳过了，所以我想这是我的索引的问题。然而，即使有 gdb 和一些细心的观察，我还是想念它。

如果你们不介意快速浏览一下这段代码，我将不胜感激。

#include <stdio.h>

void insertion_sort(int *array);

int main(void)
{
    /* 6 is a constant length of the array */
    /* could be replaced with a variable, etc in real-scenario */
    int array[6] = {5, 2, 4, 6, 1, 3};
    insertion_sort(array);

    for (int i = 0; i < 6; i++) {
        printf("%d: %d\n", i, array[i]);
    }

    return 0;
}

void insertion_sort(int *array)
{
    int j, i, key;
    for (j = 1; j < 6; j++) {
        key = array[j];
        i = j - 1;
        while (i > 0  && array[i] > key) {
            array[i+1] = array[i];
            i -= 1;
        }
        array[i+1] = key;
    }
}

Answer 1

问题出在您的 while 循环中。应该是这样的：

void insertion_sort(int *array)
{
    int j, i, key;
    for (j = 1; j < 6; j++) {
        key = array[j];
        i = j - 1;
        while (i >= 0  && array[i] > key) {
            array[i+1] = array[i];
            i -= 1;
        }
        array[i+1] = key;
    }
}

C 中的插入排序未正确迭代数组

Insertion sort in C not iterating over the array correctly

c

arrays

insertion-sort