插入排序算法，奇怪的行为

Question

我正在学习 C 编程，目前正在学习经典的插入排序算法。

为了上下文化，我有一组 3 个数组来测试：

乱序第一个
倒数第二个
最后一个是有序的，但在 2 个元素之间进行了交换。

这是我的代码：

int insertionSort(int* tab, int n){
    int i;
    for (i=1; i<n; i++){
        int j = i;
        while(tab[j] < tab[j-1]) {
            swap(&tab[j-1], &tab[j]);
            j-=1;
        }
    }
    affiche(tab, n);
    return 0;
}

对于最后两个数组，它工作正常。但是对于第一个，我得到了：

6 6 7 8 10 32521 14 15 17 19 20 21 23 25 26 28 28 28 32 32 34 35 38 38 39 43 44 46 48 49 50 58 59 62 64 65 69 71 75 79 79 79 81 84 86 89 92 93 97 99

而不是

3 6 6 7 8 10 14 15 17 19 20 21 23 25 26 28 28 28 32 32 34 35 38 38 39 43 44 46 48 49 50 58 59 62 64 65 69 71 75 79 79 79 81 84 86 89 92 93 97 99

如您所见，该算法适用于数组的大部分，但对于第六个最小值，我有随机值（有时有 92、93、97...第一个） .

我没有任何核心转储，这意味着我在内存中的数组 space 中，但是像 32521 这样的一些值让我认为我的索引 j 走得太远了内存。

老实说，我看不出问题出在哪里。

Answer 1

看看这个循环

    while(tab[j] < tab[j-1]) {
        swap(&tab[j-1], &tab[j]);
        j-=1;
    }

j可以运行到处开心。需要有一些东西可以检测到 j 不 < 0（实际上是 < 1，因为您访问 'tab[j-1]'）

可能

while((j >= 1) && (tab[j] < tab[j-1]) ) {
        swap(&tab[j-1], &tab[j]);
        j-=1;
    }

插入排序算法，奇怪的行为

Insertion sort algorithm, weird behaviour

c

sorting

insertion-sort