我正在阅读Patterson和Hennesy(第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
有什么我忘记的事情吗?如果没有,我认为第二个循环条件一定有一个错误。我已经看到了该算法的其他实现,但是我想知道如何使这种方法起作用。
我也尝试过此代码。我已经用GCC编译了它,并且以某种方式对我有用(程序的退出状态为0,数组已正确排序)。但是我也认为它们是第二循环的问题。我会将j + = 1指令更改为j- = 1。否则,第二个循环可能以无限循环结束。另外,我会将第一个循环中的i = 0指令更改为ai = 1指令,因为它将以不必要的迭代结束。
本文收集自互联网,转载请注明来源。
如有侵权,请联系 [email protected] 删除。
我来说两句