英文:
nested for loop bubble-sort logic (python)
问题
I don't fully understand the logic itself behind the for loops:
# 代码示例
array = [1, 6, 2, 8, 3, 7, 4, 9, 5]
n = len(array)
for i in range(n-1):
for j in range(n-i-1):
if array[j] > array[j+1]:
array[j], array[j+1] = array[j+1], array[j]
print(array) # 仅在此处打印数组，以便在终端中观察排序过程。
我对我的代码的混乱以及这个问题可能听起来很愚蠢感到抱歉...
我完全理解if语句，因为它只是在索引之间移动，比较和排序;
但我不是100%理解以下逻辑：
for i in range(n-1):
for j in range(len(n-i-1):
为什么第一个循环中我们使用n-1，第二个循环中为什么使用n-i-1？
英文:
(first time poster, already scared to post lol, apologies in advance, not too sure how to word my question properly but i'll give it a go!)
I don't fully understand the logic itself behind the for loops:
# example code
array = [1,6,2,8,3,7,4,9,5]
n = len(array)
for i in range(n-1):
for j in range(n-i-1):
if array[j] > array[j+1]:
array[j], array[j+1] = array[j+1], array[j]
print(array) # print array is only here so i could watch it sort in terminal.
I apologise about how messy my code is and how stupid this question must sound..
I fully understand the if statement since it's just moving along an index, comparing and sorting so to speak;
but I'm not 100% on the logic behind:
for i in range(n-1):
for j in range(len(n-i-1):
why do we do n-1 for the first loop and why do we do n-i-1 for the second loop?
答案1
得分: 1
n-i-1 在你的内循环中是正确的。它之所以存在，是因为在每一步之后，你的第(n-i-1)个元素已经就位，无需重新排序接下来的元素。
基本上，外循环的每次迭代都会找到数组中尚未排序部分的最大元素，并将其放在该部分的最后位置。每次迭代后，你会在数组的末尾正确排序i+1个元素。
英文:
n-i-1 in your inner loop is correct. It is there because after each step, your (n-i-1)th element is in place, and there is no need to re-sort next elements.
Basically, every iteration of the outer loop finds the maximum element in the still not sorted part of the array, and puts it in last place (of these unsorted part). And after each iteration, you get i+1 correctly sorted element at the end of the array.
答案2
得分: 0
对于两个循环，你肯定是用range(n-1)来做的
然而，想象一下，如果第一个项目是999999，实际上应该位于最后一个位置（在排序之后）。因此，它必须沿着数组一直从第一个位置走到最后一个位置。
在外部循环的_第一步_中，在内部循环的每一步中，999999都将被推前一位。
在外部循环的_第一步_结束时，它已经位于正确的位置在_末尾_。
现在想象一下，在外部循环的第一步中，如果999999从列表的中间开始呢？在内部循环比较到999999之前，忽略前几步：999999还没有移动。一旦比较到999999，它将在每次比较时向前推进，直到达到列表的末尾：它的正确位置。
因此，在外部循环的一步之后，999999肯定会正确地定位
剩下的只是剩下的项目，后面跟着的是已经位于正确位置的999999。如果在将来的外部循环中将其与其他元素进行比较，它将不会移动。因此，甚至在进行外部循环的第二步（以及之后的步骤）时，我们都可以省略内部循环的最后一次比较。
归纳
外部循环的_第二步_实际上只需要对除了最后一个项目以外的所有项目进行排序。
然后，外部循环的_第三步_只需要对“除了最后两个”的项目进行排序。
等等。
英文:
You certainly do it with range(n-1) for both loops
However, imagine if the first item was 999999 and actually belongs in the last position (after sorting). It therefore has to step along the array all the way from first to last position.
During just the first step of the outer loop, on every step of the inner loop, the 999999 will be pushed forward by one position.
By the end of the first step of the outer loop, it will already be in the correct position at the end.
Now think what would happen during the first step of the outer loop, if the 999999 had started half-way along the list? Ignore the first few steps, before inner-loop comparisons reached 999999: the 999999 is not yet moving. Once the comparisons reach the 999999, it will advance on every comparison until it gets to the end of the list: it's correct position.
Therefore after one step of the outer loop, the 999999 will definitely be correctly positioned
What remains is only the remaining items, followed by the 999999 which is definitely in the correct place already. If it is compared on future outer loops, it will not move. So there is no need to even compare it. We can omit the final comparison of the inner loop, when doing the second step (and beyond) of the outer loop.
Induction
The second step of the outer loop really only needs to sort all-but-the-last items.
And then the third step of the outer loop only needs to sort the "all-but-last-two" items.
Etc.
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论