堆栈溢出我一直在研究算法,这样我就可以把它们一块一块地分解,了解发生了什么。无论如何,我正在看这个教程,看看冒泡排序。我对c++中演示算法的一小部分感到困惑,整数j。
void bubbleSort(int arr[], int n) {
bool swapped = true;
int j = 0;
int tmp;
while (swapped) {
swapped = false;
j++;
for (int i = 0; i < n - j; i++) {
if (arr[i] > arr[i + 1]) {
tmp = arr[i];
arr[i] = arr[i + 1];
arr[i + 1] = tmp;
swapped = true;
}
}
}
}
是算法的必要部分吗?我真的不明白它在做什么,因为当我在for循环中将j换成1时,我得到了相同的结果。
for (int i = 0; i < n - 1; i++)
TL;博士:为什么整型j会出现在算法中?
在第一次外部迭代中,我们将最大的整数泡入a[n-1]
。第二次迭代只需要遍历数组中剩余的未排序部分,即从索引0到n-2,并将第二大整数冒泡到a[n-2]
中。第三次迭代只需要从索引0遍历数组到n-3,以此类推。
变量j
通过限制数组在随后的外部迭代中遍历的范围来实现这一点。我们可以很好地在每次迭代中遍历整个数组(就像用n-1
更改n-j
之后所做的那样)并获得相同的结果。但这将是低效的,因为我们将不必要地在每次迭代中比较数组中已排序部分的元素。如果您有任何问题,请告诉我。
当冒泡排序在列表中工作时,它会将较大的数字交换到列表的末尾。这意味着在算法的每次迭代中,最后的元素都保证被排序。如果最后的元素已排序,则没有必要重新访问它们以再次排序。n-j
通过限制在任何迭代中访问列表的范围来防止这种情况。如果j
随着算法的进行而增长,n-j
就会收缩。
不要只是查看代码,而是在调试器中启动它,这几乎肯定是与您的开发环境一起提供的(如果您没有带有调试器的开发环境,那么您早就应该纠正这一点了)。调试器可能是程序员所拥有的最具生产力的工具),并逐步检查代码。观察列表发生了什么变化,以及每次迭代所访问的列表的范围。
调试器不仅仅是一个修复代码的好工具,它也是一个很好的教育工具。
变量j用于将最大的数字向右移动。在每次迭代中,我们通过第一步将指针从n(最初n-j=n, j= 0)移动到0。最后,我们有一个排序数组