泡泡糖

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)

现在，这个（据我所知）排序正确，但一旦它完成，它就无限循环。

如何修复此代码，以便函数正确地完成对任何（合理）大小的列表的排序？

p.S.我知道我不应该在函数中真正有prints，我应该有一个return，但是我还没有这么做，因为我的代码还没有真正工作。

Answer 1

为了解释为什么您的脚本现在不能工作，我将把变量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作为“index”。

  for i in range(0, length):
  

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

  for i in range(length):
  

• Python Style Guide建议用小写和下划线命名变量。对于这样一个小脚本来说，这是一个非常小的挑剔；更重要的是让您习惯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

（顺便说一句，我也删除了你的打印声明。）

Answer 2

这就是当使用负意义的变量名时，需要反转它们的值。以下内容更容易理解：

sorted = False
while not sorted:
    ...

另一方面，算法的逻辑有点偏离。您需要检查在for循环期间是否交换了两个元素。以下是我的写作方法：

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 3

气泡排序的目标是在每一轮中移动底部的较重的项，同时向上移动较轻的项。在比较元素的内部循环中，不必每次都迭代整个列表。最重的已经排在最后。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