泡泡排序作业

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才会保留.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的风格指南建议变量用下划线小写字母来命名.对于像这样的小脚本来说,这是一个非常小的挑剔; 它让你习惯于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

冒泡排序的目的是在每一轮中移动较重的物品,同时将较轻的物品向上移动.在内部循环中,您比较元素,您不必在每个回合中迭代整个列表.将最重的已经放在最后.该交换变量是一个额外的检查,所以我们可以标记列表现在可以正确排序,并避免不必要的计算仍在继续.

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 = 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 4

你使用Unsorted变量是错误的; 你想要一个变量,告诉你是否交换了两个元素; 如果你已经这样做了,你可以退出你的循环,否则你需要再次循环.要修复你在这里得到的东西,只需将"unsorted = false"放在你的if案例的正文中; 删除你的其他情况; 并在for循环之前放置"unsorted = true" .

Answer 5

def bubble_sort(l):
    for passes_left in range(len(l)-1, 0, -1):
        for index in range(passes_left):
            if l[index] < l[index + 1]:
               l[index], l[index + 1] = l[index + 1], l[index]
    return l