为什么我的Python冒泡排序这么慢？

Question

我有一段代码，它使用冒泡排序来反转一个列表，但在最坏的情况下性能很差：

for i in xrange(len(l)):
    for j in xrange(len(l)):
        if l[i]>l[j]:
            l[i], l[j] = l[j], l[i]

在某些情况下（比如当 len(l) = 100000 时），这段代码执行超过2小时，我觉得这很奇怪，请帮我修正代码或者给点建议。numpy 和 numarray 的解决方案也欢迎。

Answer 1

冒泡排序可能被认为是非常糟糕和慢的算法，但你更愿意用一个处理100个项目的O(N^2)算法，还是一个需要拨号上网的O(1)算法呢？

而且，处理100个项目不应该花费2个小时。我不太懂Python，但你是不是在进行赋值时把整个列表都复制了一遍？

这是一个用Python写的冒泡排序（我从谷歌找的，因为我懒）：

def bubbleSort(theList, max):
    for n in range(0,max): #upper limit varies based on size of the list
        temp = 0
        for i in range(1, max): #keep this for bounds purposes
            temp = theList[i]
            if theList[i] < theList[i-1]:
                theList[i] = theList[i-1]
                theList[i-1] = temp

还有一个来自维基百科的例子：

def bubblesort(l):
    "Sorts l in place and returns it."
    for passesLeft in range(len(l)-1, 0, -1):
        for index in range(passesLeft):
            if l[index] < l[index + 1]:
               l[index], l[index + 1] = l[index + 1], l[index]
    return l

冒泡排序的复杂度是N(N-1)。这基本上就是N^2，因为你需要扫描列表并比较每一个元素。

顺便说一下，你可能会发现C++是最快的，其次是Java，然后是Python。

Answer 2

这不太像冒泡排序……除非我犯了个小错误，这个更像是一个Python的冒泡排序：

swapped = True
while swapped:
  swapped = False
  for i in xrange(len(l)-1):
    if l[i] > l[i+1]:
      l[i],l[i+1] = l[i+1],l[i]
      swapped = True

冒泡排序的核心思想是“气泡”在数组中移动，交换相邻的值，直到它遍历完列表时没有再进行任何交换。可以做一些优化（比如缩小内层循环的大小），但通常只有在你做作业的时候才值得去考虑这些优化。

编辑：修正了 length() -> len() 的错误。

Answer 3

冒泡排序是一种很糟糕的排序算法。这可能就是它不受欢迎的原因。如果你需要排序速度快一点，我建议你试试其他算法，比如快速排序或者归并排序。