冒泡排序c程序中可能的错误

Question

我正在阅读 Patterson 和 Hennesy 合着的书 "Computer Organization and Design"（第 5 版），发现了这个冒泡排序代码：

void sort (int v[], int n)
{
    int i,j;
    for (i=0; i<n; i+=1) {
        for (j = i-1; j>=0 && v[j] > v[j+1]; j+=1) {
            swap(v,j);
        }
    }
}

void swap (int v[], int k) {
    int temp;
    temp = v[k];
    v[k] = v[k+1];
    v[k+1] = temp;
}

我不明白这个函数如何对数组进行排序。特别是如果数组的第一个元素也是最大的，在我看来索引 j 会越界。运行代码和打印索引证实了这一点。

这是我使用的代码：

#include <stdio.h>

void swap (int v[], int k) {
    int temp;
    temp = v[k];
    v[k] = v[k+1];
    v[k+1] = temp;
}

void sort (int v[], int n)
{
    int i,j;
    for (i=0; i<n; i+=1) {
        printf("%d \n", i);
        for (j = i-1; j>=0 && v[j] > v[j+1]; j+=1) {
            printf("%d, %d \n", i, j);
            swap(v,j);
        }
    }
}

int main() {
    int x[3] = {5,1,2};
    int N = 3;

    sort(x, N);
    for(int i = 0; i < 3; i++) {
        printf("%d ", x[i]);
    }
    return 0;
}

这是结果：

/Users/mauritsdescamps/Desktop/test/cmake-build-debug/test
0 
1 
1, 0 
1, 1 
1, 2 
1, 3 
1, 4 
2 
2, 1 
2, 2 
2, 3 

Process finished with exit code 6

我是不是忘记了什么？如果不是，我想肯定是第二个循环条件出错了。我已经看到该算法的其他实现，但我想知道如何使这种方法起作用。

Answer 1

我也试过这段代码。我用 GCC 编译了它，不知何故它对我有用（程序的退出状态是 0，数组被正确排序）。但我也认为他们是第二个循环的问题。我会将 j+= 1 指令更改为 j-=1。否则第二个循环可能会以无限循环结束。此外，我会将第一个循环中的 i=0 指令更改为 i=1 指令，因为它会以不必要的迭代结束。

冒泡排序c程序中可能的错误

Possible mistake in bubble sort c program

c

indexing

bubble-sort

indexoutofboundsexception