为什么我在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

冒泡排序是一种可怕的排序算法.这很可能就是原因.如果需要速度,我会尝试另一种算法,如快速排序或合并排序.

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

请注意,整个想法是"气泡"沿着数组移动,交换相邻值,直到它在列表中移动,没有任何交换.可以进行一些优化(例如缩小内循环的大小),但是当你"面向家庭作业"时,它们通常只值得打扰.

编辑:固定长度() - > len()

Answer 3

冒泡排序可能会很糟糕,也可能很慢,但你更喜欢O(N ^ 2)算法超过100项,还是O(1)需要拨号连接？

100个项目的清单不应该花费2个小时.我不知道python,但你做这些任务时是否有机会复制整个列表？

这是Python中的冒泡排序(来自Google,因为我很懒):

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 4

numpy解决方案是什么意思？Numpy有一些排序设施,对于那些相当小的数组是不稳定的:

import numpy as np
a = np.random.randn(100000)
# Take a few ms on a decent computer
np.sort(a)

有三种可用的排序算法,平均每个都是Nlog(N).