为什么冒泡排序中的范围循环是相反的？

Question

我是 Python 的新手，正在 Python 学习数据结构。我正在尝试在 python 中实现冒泡排序算法，我做得很好，但没有得到正确的结果。然后我找到一些教程，在那里我看到他们首先设置一个用于检查的基础范围。

所以python中range的语法是：

range([start], stop[, step])

冒泡排序算法为：

def bubbleSort(alist):

   for i in range(len(alist) - 1, 0, -1):
       for j in range(i):

           if alist[j] > alist[j+1]:
               temp = alist[j]
               alist[j] = alist[j+1]
               alist[j+1] = temp

   return alist

print(bubbleSort([5, 1, 2, 3, 9, 8, 0]))

我了解该算法的所有其他逻辑，但我无法理解为什么循环从列表末尾开始一直持续到列表的第一个元素：

for i in range(len(alist) - 1, 0, -1):

为什么要反向遍历列表？这个循环的主要目的只是设置范围条件所以为什么我们不能像这样从第一个元素遍历到 len(list) - 1:

for i in range(0, len(alist) - 1, 1):

Answer 1

这是因为当你从列表的开头冒泡到最后时，最后的结果是列表中的最后一项将被排序（你已经将最大的项目冒泡到最后）。因此，您不想在执行下一个气泡时将列表中的最后一项包括在内（您知道它已经在正确的位置）。这意味着您需要排序的列表会变得更短，从末尾开始向下延伸到开头。在这段代码中，i 始终是剩余未排序列表的长度。

Answer 2

您可以将其用于：

for i in range(0,len(alist)-1,1):

但因此您应该更改第二次迭代：

for j in range(0,len(alist)-i,1):

我认为在第一行使用反向迭代的目的是为了简化第二次迭代。这是使用 python

的优势

作为@Jeremy McGibbon 的回答，冒泡排序背后的逻辑是避免 j 到达列表后面的 "sorted part" 。使用示例代码时，j 范围将随着 i 值的减小而减小。当您将 i 更改为增加时，您应该以不同的方式处理 j 迭代

Answer 3

在您的代码中，索引 i 是内循环在交换元素时将考虑的最大索引。冒泡排序的工作方式是通过交换兄弟元素将最大的元素移到右边。

这意味着在第一次外部迭代（或内部循环的第一个完整循环）之后，列表中最大的元素位于列表的远端。所以它已经在正确的位置，不需要再考虑了。这就是为什么对于下一次迭代，i 是 少一个 以跳过最后一个元素，只查看项目 0..len(lst)-1.

然后在下一次迭代中，最后两个元素将被正确排序，因此只需要查看第0..len(lst)-2项，依此类推。

所以你想递减 i 因为列表末尾越来越多的元素已经在正确的位置并且不需要再看了。你不必那样做；你也可以总是让内循环一直走到最后，但你 不需要 ，所以你可以通过不这样做来跳过一些迭代。

I asked why we are going reverse in the list like len(list)-1,0. Why are we not going forward way like 0,len(list)-1?

我希望上面的解释已经涵盖了这一点，但让我们详细介绍一下。尝试在外循环的末尾添加一个 print(i, alist) 。所以你得到 i:

每次迭代的结果

>>> bubbleSort([5, 1, 3, 9, 2, 8, 0])
6 [1, 3, 5, 2, 8, 0, 9]
5 [1, 3, 2, 5, 0, 8, 9]
4 [1, 2, 3, 0, 5, 8, 9]
3 [1, 2, 0, 3, 5, 8, 9]
2 [1, 0, 2, 3, 5, 8, 9]
1 [0, 1, 2, 3, 5, 8, 9]

如您所见，列表将从右到左排序。这对我们的索引 i 很有效，它将限制内部循环的范围：例如，对于 i = 4，我们已经在末尾有 3 个排序元素，因此内部循环只需要查看在前 4 个元素。

现在，让我们尝试将 range 改为另一个方向。循环将是 for i in range(0, len(alist))。然后我们得到这个结果：

>>> bubbleSort([5, 1, 3, 9, 2, 8, 0])
0 [5, 1, 3, 9, 2, 8, 0]
1 [1, 5, 3, 9, 2, 8, 0]
2 [1, 3, 5, 9, 2, 8, 0]
3 [1, 3, 5, 9, 2, 8, 0]
4 [1, 3, 5, 2, 9, 8, 0]
5 [1, 3, 2, 5, 8, 9, 0]
6 [1, 2, 3, 5, 8, 0, 9]

如您所见，这根本没有排序。但为什么？ i 仍然限制了内部循环的范围，所以在 i = 1 处，循环将只查看第一对并对其进行排序；其余的将保持不变。在 i = 2，循环将查看前两对并交换它们（一次！）；其余的将保持不变。等等。当内部循环到达最后一个元素（仅在最后一次迭代中）时，没有足够的迭代来将零（也恰好是最小的元素）交换到最左边。

这又是因为冒泡排序首先将最大的元素排序到最右边。所以我们必须通过使内部循环能够完全到达右侧来启动算法。只有当我们确定那些元素在正确的位置时，我们才能停止那么远。

有一种方法来使用递增外循环：首先对最小的元素进行排序。但这也意味着我们必须在最右侧开始内部循环，以确保在寻找最小元素时检查所有元素。所以我们真的必须让这些循环朝相反的方向发展。

Answer 4

你可以这样写代码

lst = [9,6,5,7,8,3,2,1,0,4]
lengthOfArray = len(lst) - 1

for i in range(lengthOfArray):
    for j in range(lengthOfArray - i):
        if lst[j] > lst[j + 1]:
            lst[j], lst[j + 1] = lst[j + 1], lst[j]

print(lst)

为什么冒泡排序中的范围循环是相反的？

Why is the range loop in bubble sort reversed?

python

sorting

bubble-sort