英文:
Why does Bubble Sort outer loop end at n-1?
问题
我找到了这个冒泡排序（这是我学习的第一个排序算法），我几乎完全理解了它，但有一个地方让我困惑。
public static int[] bubbleSort(int[] tempArray) {
int i, j, temp, n = tempArray.length;
boolean swapped;
for (i = 0; i < n - 1; i++) {
swapped = false;
for (j = 0; j < n - i - 1; j++) {
if (tempArray[j] > tempArray[j + 1]) {
temp = tempArray[j];
tempArray[j] = tempArray[j + 1];
tempArray[j + 1] = temp;
swapped = true;
}
}
if (swapped == false)
break;
}
return tempArray;
}
在外部循环中，“n - 1”除了有助于使内部循环（n - i - 1）变短之外，还有什么作用呢？我尝试移除“n - 1”，并让计数在内部循环中起作用，结果是一样的，那么它的原因是什么呢？谢谢！
英文:
I found this bubble sort (first sort I'm ever studying), I understand it almost fully but I'm stuck on one spot.
public static int[] bubbleSort(int[] tempArray) {
int i, j, temp, n = tempArray.length;
boolean swapped;
for (i = 0; i < n - 1; i++) {
swapped = false;
for (j = 0; j < n - i - 1; j++) {
if (tempArray[j] > tempArray[j + 1]) {
temp = tempArray[j];
tempArray[j] = tempArray[j + 1];
tempArray[j + 1] = temp;
swapped = true;
}
}
if (swapped == false)
break;
}
return tempArray;
}
what is the point of "n - 1" in outer loop besides helping to make inner loop (n - i - 1) shorter? I tried removing the "n -1" and having count++ to work in the inner loop and the result was the same, so what is the reason for it then? Thanks!
答案1
得分: 2
这是因为在第一次迭代中，最大的元素已经被排序。
一张图片胜过千言万语。
图片来源：https://en.wikipedia.org/wiki/Bubble_sort
此外，最后一个元素是不需要的，因为冒泡排序是关于交换相邻元素的，而最后一个元素没有相邻元素。
英文:
It is because the largest element is already sorted in the first iteration.
A picture is worth a thousand words
Image is from https://en.wikipedia.org/wiki/Bubble_sort
Additional there is no need for the last element because bubble sort is all about swapping adjacent element and the last element doesn't have adjacent element.
答案2
得分: 1
这是因为冒泡排序是基于相邻元素交换的。如果外部循环执行到 n，那么在内部循环中就无法选择另一个元素。
temp = tempArray[j];
tempArray[j] = tempArray[j + 1];
tempArray[j + 1] = temp;
这是因为数组的大小是到 n，内部循环在 j 和 j+1 之间进行交换。
如有进一步疑问，请随意提问。
英文:
It is because bubble sorting works on swapping of adjacent element.
If outer loop goes till n then in the inner loop you cannot pick another element.
temp = tempArray[j];
tempArray[j] = tempArray[j + 1];
tempArray[j + 1] = temp;
This is because the size of array is till n and inner loop swap between j and j+1.
Feel free to ask further doubts.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论