泡泡排序作业

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)

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

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

PS：我知道我实际上不应该在函数中具有打印功能，而应该返回值，但是我还没有这样做，因为我的代码还没有真正起作用。

Answer 1

为了解释为什么您的脚本现在无法正常工作，我将变量重命名unsorted为sorted。首先，您的列表尚未排序。当然，我们设置sorted为False。一旦开始while循环，我们就假定该列表已经排序。想法是这样的：一旦找到两个顺序不正确的元素，我们就sorted回到False。只有没有顺序错误的元素sorted才会保留。Truesorted = False  # We haven't started sorting yetwhile 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样式指南》建议使用下划线将变量命名为小写。对于这样的小脚本，这是一个很小的缺点。它会让您习惯于Python代码最常类似于的东西。def bubble(bad_list):要交换两个变量的值，请将它们写为元组分配。右侧被评估为元组（例如(badList[i+1], badList[i])is (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

气泡分类的目的是在每轮底部移动较重的物品，同时向上移动较轻的物品。在内部循环中，您可以在其中比较元素，而不必每次都迭代整个列表。将最重的已经放在最后。该交换变量是一个额外的检查，所以我们可以标记列表现在可以正确排序，并避免不必要的计算仍在继续。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

当您使用负含义的变量名时，您需要反转它们的值，这就是这种情况。以下内容将更容易理解：sorted = Falsewhile 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