为什么冒泡排序实现无限循环？

Question

在课堂上，我们正在学习排序算法。虽然我在讨论这些算法和写伪代码的时候理解得很好，但在写实际代码时遇到了问题。

这是我在Python中的尝试：

mylist = [12, 5, 13, 8, 9, 65]

def bubble(badList):
    length = len(badList) - 1
    unsorted = True

    while unsorted:
        for element in range(0,length):
            unsorted = False
            if badList[element] > badList[element + 1]:
                hold = badList[element + 1]
                badList[element + 1] = badList[element]
                badList[element] = hold
                print badList
            else:
                unsorted = True

print bubble(mylist)

现在，这段代码（就我所知）排序是正确的，但一旦完成，它就会无限循环。

我该如何修复这段代码，让这个函数能够正确结束，并且能够对任何（合理大小的）列表进行排序呢？

附注：我知道在函数中不应该有打印语句，应该有返回值，但由于我的代码还没有真正工作，所以我还没有做到这一点。

Answer 1

当你使用带有负面含义的变量名时，就会出现这种情况，你需要反转它们的值。下面的写法会更容易理解：

sorted = False
while not sorted:
    ...

另一方面，这个算法的逻辑有点问题。你需要检查在循环中是否有两个元素被交换。以下是我会写的方式：

def bubble(values):
    length = len(values) - 1
    sorted = False
    while not sorted:
        sorted = True
        for element in range(0,length):
            if values[element] > values[element + 1]:
                 hold = values[element + 1]
                 values[element + 1] = values[element]
                 values[element] = hold
                 sorted = False
    return values

Answer 2

冒泡排序的目的是在每一轮中把重的东西往下移，把轻的东西往上移。在内部循环中，也就是你比较元素的地方，你不需要每次都遍历整个列表。因为最重的东西已经放在最后了。swapped这个变量是一个额外的检查，用来标记列表现在已经排好序了，这样就可以避免继续进行不必要的计算。

def bubble(badList):
    length = len(badList)
    for i in range(0,length):
        swapped = False
        for element in range(0, length-i-1):
            if badList[element] > badList[element + 1]:
                hold = badList[element + 1]
                badList[element + 1] = badList[element]
                badList[element] = hold
                swapped = True
        if not swapped: break

    return badList

你的版本1，已修正：

def bubble(badList):
    length = len(badList) - 1
    unsorted = True
    while unsorted:
        unsorted = False
        for element in range(0,length):
            #unsorted = False
            if badList[element] > badList[element + 1]:
                 hold = badList[element + 1]
                 badList[element + 1] = badList[element]
                 badList[element] = hold
                 unsorted = True
                 #print badList
             #else:
                 #unsorted = True

     return badList

Answer 3

为了说明为什么你的脚本现在不工作，我将把变量 unsorted 改名为 sorted。

一开始，你的列表还没有排序。当然，我们把 sorted 设置为 False。

当我们开始 while 循环时，我们假设列表已经是排好序的。这个想法是这样的：一旦我们发现两个元素的顺序不对，我们就把 sorted 重新设置为 False。只有当没有元素的顺序不对时，sorted 才会保持为 True。

sorted = False  # We haven't started sorting yet

while not sorted:
    sorted = True  # Assume the list is now sorted
    for element in range(0, length):
        if badList[element] > badList[element + 1]:
            sorted = False  # We found two elements in the wrong order
            hold = badList[element + 1]
            badList[element + 1] = badList[element]
            badList[element] = hold
    # We went through the whole list. At this point, if there were no elements
    # in the wrong order, sorted is still True. Otherwise, it's false, and the
    # while loop executes again.

还有一些小问题可以让代码更高效或更易读。

• 在 for 循环中，你使用了变量 element。从技术上讲，element 其实并不是一个元素，它是一个表示列表索引的数字。而且，这个名字有点长。在这种情况下，可以用一个临时的变量名，比如 i 来表示“索引”。

  for i in range(0, length):
  

• range 命令也可以只接受一个参数（叫做 stop）。在这种情况下，你会得到一个从 0 到这个参数的所有整数的列表。

  for i in range(length):
  

• Python 风格指南 建议变量名使用小写字母并用下划线分隔。这对像这样的简单脚本来说是个小问题；更多的是让你习惯 Python 代码通常是什么样子的。

  def bubble(bad_list):
  

• 要交换两个变量的值，可以使用元组赋值的方式。右边的部分会被计算为一个元组（比如 (badList[i+1], badList[i]) 可能是 (3, 5)），然后赋值给左边的两个变量（(badList[i], badList[i+1])）。

  bad_list[i], bad_list[i+1] = bad_list[i+1], bad_list[i]
  

把这些都放在一起，你就得到了这个：

my_list = [12, 5, 13, 8, 9, 65]

def bubble(bad_list):
    length = len(bad_list) - 1
    sorted = False

    while not sorted:
        sorted = True
        for i in range(length):
            if bad_list[i] > bad_list[i+1]:
                sorted = False
                bad_list[i], bad_list[i+1] = bad_list[i+1], bad_list[i]

bubble(my_list)
print my_list

（顺便说一下，我也去掉了你的打印语句。）