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

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)

据我所知，以下代码可以正确排序，但是一旦完成排序，它就会无限循环。

如何修复此代码，使函数能够正确排序任何（合理大小的）列表并正常结束？

附言：我知道在一个函数中不应该有打印语句，并且应该有一个返回语句，但是因为我的代码还没有完全工作，所以我还没有这样做。

- Josh Hunt

---

天啊，这真让我恼火。为什么他们要一开始就教这种毫无用处的算法呢？不是针对问题本身，而是针对它的来源。 - Matt Davison

这篇文章的主要内容是：“我写代码有困难，这是我所做的，但它并没有奏效。” 很明显，隐含着“有人能否给我一些指点？” 与许多作业问题不同的是，这篇文章（a）写得很好，（b）坦率地说明了这是作业，（c）包括对解决问题的良好尝试。 我认为缺少实际问号并不会太大影响。 - John Fouhy

冒泡排序被用作学习工具，因为它是大多数人最容易理解的排序算法。它是了解排序和算法的良好入门点。如果我们只教授人们实际使用的东西，那么有关排序的讨论将以“使用库排序例程”开始和结束。 - Bill the Lizard

这个问题是如何提出一个好的“作业”问题的典范。正如约翰·福伊所说，它包含了一个代码示例，而且写得很好，提问者也在努力让我们更容易给出帮助。做得好，乔什·亨特。 - Jarret Hardie

冒泡排序并不是一种容易被人们理解的排序算法。从我的经验以及教学经验来看，我可以自信地说，插入排序、选择排序、最小元素排序、甚至（对于某些学生来说）归并排序和快速排序都更容易理解——毕竟它们对应着一些比较自然的排序方式，但是冒泡排序只不过是一种人为制造的排序方式。此外，冒泡排序容易出现许多差一错误和无限循环错误，就像这里提出的问题一样。正如 Knuth 所说：“冒泡排序似乎没有什么值得推荐的地方，除了一个引人注目的名字......” - ShreevatsaR

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.

还有一些小问题可以帮助代码更高效、更易读。

• In the for loop, you use the variable element. Technically, element is not an element; it's a number representing a list index. Also, it's quite long. In these cases, just use a temporary variable name, like i for "index".

  for i in range(0, length):
  

• The range command can also take just one argument (named stop). In that case, you get a list of all the integers from 0 to that argument.

  for i in range(length):
  

• The Python Style Guide recommends that variables be named in lowercase with underscores. This is a very minor nitpick for a little script like this; it's more to get you accustomed to what Python code most often resembles.

  def bubble(bad_list):
  

• To swap the values of two variables, write them as a tuple assignment. The right hand side gets evaluated as a tuple (say, (badList[i+1], badList[i]) is (3, 5)) and then gets assigned to the two variables on the left hand side ((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

（我顺便把你的打印语句也删除了。）

- Wesley

---

就最后这段代码而言，bubble函数没有返回值，因此最终结果是打印出“None”。您可能想要返回列表，或者在调用bubble(my_list)之后再打印my_list。 - Tung Nguyen

+1 结构良好，建议明确。很高兴看到您引导读者了解您的做法和原因，而不只是快速提供解决方案。 - Tom Leys

我是一名C＃程序员，所以这可能只是因为我不理解Python，但是在while循环中您不需要一些代码来从长度中减去1，以获取正常的冒泡排序算法吗？ - Martin Brown

这是一个天真（但不是错误的）冒泡排序实现。在每次while循环迭代后，最大的元素“冒泡”到列表的末尾。因此，在一次迭代后，最后一个元素肯定处于正确的位置（并且不会被连续的迭代移动）。通过从长度中减去1，您可以通过仅对未排序的子列表（列表的前面length-n个元素）进行排序来优化算法。我选择跳过这种优化，因为它更多地是一种优化而不是算法的重要部分。 - Wesley

把所有的东西放在一起，你就得到了这个：...哦，你错过了这一个：“range”命令也可以只带一个参数（名为stop）。 - Peter Perháč

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

你的第一个版本，已经更正：

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

- Nick Dandoulakis

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

- Martin Cote

---

有点遗憾的是，我无法为这个答案点击一个“WRONG”按钮。我认为这个问题和回答 - 特别是投票 - 需要在下一次Joel Spolsky谈论他如何调整stackoverflow上的社交互动时进行特别介绍。 - Daniel Martin

@Jonathan - 我确实给它投了反对票，但仅仅是这样似乎还不够。（它比“没有帮助”更糟糕）我承认，变量名倒置会让阅读代码的人感到困惑，但这并不是这个回答的主要问题。主要问题是完全错误的。 - Daniel Martin

你们说得对，我在这个问题上回答得过早了。非常抱歉。 - Martin Cote

@Martin - 我应该指出，我对投票的结果感到更加惊讶和震惊，而不是答案本身。声望系统鼓励你立即给出第一个答案。问题在于错误的答案也会被投票赞成。 - Daniel Martin

我怀疑大多数人投票时并没有真正理解问题（就像我回答问题的方式一样）。另一方面，提问者有特权在之后选择“正确”的答案。 - Martin Cote

Answer 4

您对Unsorted变量的使用是错误的；您需要一个变量来告诉您是否已经交换了两个元素；如果您已经这样做了，可以退出循环，否则，您需要再次循环。要修复您在此处的问题，只需将“unsorted = false”放在if语句的主体中；删除else语句；并在for循环之前放置“unsorted = true”。

- Paul Sonier

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

- mtasic85

---

我相信问题更多地是关于“如何修复这段代码”，而不是“你的冒泡排序是什么？” - Josh Hunt

您说得完全正确，但以正确的方式去做更加重要。 - mtasic85

的确，也许是这样，但任何被标记为作业的内容最好在调整后而不是重写（特别是当它是由提问者标记为作业时）。 - Jarret Hardie

这是对于大多数人学习的C语言冒泡排序算法教材进行完美重写。我写了同样的内容。 - lprsd

在我看来，添加好的信息是有帮助的。所以好的答案..你可能会使用标志尽早中断。 - Grijesh Chauhan

Answer 6

#一个非常简单的函数，可以通过减少第二个数组的问题空间进行优化（显然）。但复杂度仍为O(n^2)。

def bubble(arr):
    l = len(arr)        
    for a in range(l):
        for b in range(l-1):
            if (arr[a] < arr[b]):
            arr[a], arr[b] = arr[b], arr[a]
    return arr 

- Waqas

---

在Python中，你可以通过以下方式轻松交换变量的值：arr[a], arr[b] = arr[b], arr[a]。 - Makoto

Answer 7

def bubble_sort(a):
    t = 0
    sorted = False # sorted = False because we have not began to sort
    while not sorted:
    sorted = True # Assume sorted = True first, it will switch only there is any change
        for key in range(1,len(a)):
            if a[key-1] > a[key]:
                sorted = False
                t = a[key-1]; a[key-1] = a[key]; a[key] = t;
    print a

- pinkopink

Answer 8

def bubbleSort(alist):
if len(alist) <= 1:
    return alist
for i in range(0,len(alist)):
   print "i is :%d",i
   for j in range(0,i):
      print "j is:%d",j
      print "alist[i] is :%d, alist[j] is :%d"%(alist[i],alist[j])
      if alist[i] > alist[j]:
         alist[i],alist[j] = alist[j],alist[i]
return alist

alist = [54,26,93,17,77,31,44,55,20,-23,-34,16,11,11,11]

打印 bubbleSort(alist)

- pythonnewbie

---

请正确缩进您的代码示例：当然，在Python中，这尤其重要。您可能还想解释一下为什么考虑您的解决方案是值得的，因为也有一个获得 100 票的答案。 - kdopen

Answer 9

你的代码里有几个错误。第一个是长度问题，第二个是使用了未排序的列表（正如McWafflestix所说）。如果你要打印输出，你可能还想返回这个列表：

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

def bubble(badList):
    length = len(badList) - 2
    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
                unsorted = True

    return badList

print bubble(mylist)

更新：你说得对，上面的代码有很多问题。我没有测试更多的例子，我的错。

def bubble2(badList):
    swapped = True
    length = len(badList) - 2

    while swapped:
        swapped = False
        for i in range(0, length):
            if badList[i] > badList[i + 1]:

                # swap
                hold = badList[i + 1]
                badList[i + 1] = badList[i]
                badList[i] = hold

                swapped = True

    return badList

- Trevor Oke

---

“unsorted = False” 不应该放在 for 循环之外吗？ - Svante

它有比那更多的问题 ;) - Trevor Oke

Answer 10

我是一个新手，昨天开始阅读有关Python的内容。受到您的示例的启发，我创建了一些可能更具80年代风格的东西，但它仍然可以工作。

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

i=0
while i < len(lista1)-1:
    if lista1[i] > lista1[i+1]:
        x = lista1[i]
        lista1[i] = lista1[i+1]
        lista1[i+1] = x
        i=0
        continue
    else:
        i+=1

print(lista1)

- Igor