我有以下代码使用冒泡排序来反转列表并且时间性能最差：
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解决方案是受欢迎的。
问问题
6097 次
18 回答
25
冒泡排序是一种可怕的排序算法。这很可能是原因。如果需要速度，我会尝试另一种算法，例如快速排序或合并排序。
于 2009-06-15T17:30:01.433 回答
13
这不是一个冒泡排序......除非我犯了一个微不足道的错误，否则这将更接近于 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（）
于 2009-06-15T17:43:02.343 回答
6
冒泡排序可能很糟糕而且很慢等，但是您更愿意使用超过 100 个项目的 O(N^2) 算法，还是需要拨号连接的 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。
于 2009-06-15T17:50:32.943 回答
5
numpy 解决方案是什么意思？Numpy 有一些排序工具，对于那些相当小的数组来说是即时的：
import numpy as np
a = np.random.randn(100000)
# Take a few ms on a decent computer
np.sort(a)
有 3 种排序算法可用，平均为 Nlog(N)。
于 2009-06-15T18:01:21.777 回答
4
我相信您提到过您试图将其用作比较速度的基准。
我认为通常 Python 比 Ruby 快一点，但不是很接近 Java/C/C++/C#。Java 是 C 的 2 倍以内，但所有解释型语言都慢了大约 100 倍。
您可能会在 Google 上搜索“编程语言游戏”以获取大量应用程序/语言/等的比较。查看 Python JIT 以获得更好的性能。
您也可以将其与 Ruby 进行比较，以了解更公平的测试。
编辑：只是为了好玩（与问题无关）检查这个 -
public class Test {
public static void main(String[]s) {
int size=Integer.valueOf(s[0]).intValue();
Random r=new Random();
int[] l=new int[size];
for(int i=0;i<size;i++)
l[i]=r.nextInt();
long ms=(new Date()).getTime();
System.out.println("built");
if(fast) {
Arrays.sort(l);
else {
int temp;
for(int i=0;i<size;i++)
for(int j=0;j<size;j++)
if(l[i]>l[j]) {
temp=l[i];
l[j]=l[i];
l[j]=temp;
}
}
ms=(new Date()).getTime()-ms;
System.out.println("done in "+ms/1000);
}
}
有趣的是：Java 运行时间是这样的：
数组大小 慢时间 快时间 100k 2s 0s 1M 23s 0s 10M 39m 2s 100M NO 23s
并不是说这个添加与这个问题有任何关系，而是内置的执行速度很快。我认为生成时间比排序时间长（猜猜这对调用 Random 和内存分配很有意义。）
必须进入 CLI 和 -Xmx1000M 才能让最后一个运行。
于 2009-06-15T18:51:44.057 回答
3
冒泡排序使 O(N 2 ) 比较操作（或迭代）。对于 N = 100,000，这意味着将有 10,000,000,000 次迭代。如果这需要 2 小时（称之为 10,000 秒），那么这意味着您每秒获得 1,000,000 次迭代 - 或每次迭代 1 微秒。这速度不算快，但也不算太差。我在挥手，忽略了不断的乘法因素。
如果您使用快速排序，那么您将获得 Nlog(N) 次迭代，这意味着大约 1,000,000 次迭代，总共需要 1 秒。（log 10 (N) 为 5；为简单起见，我将其四舍五入为 10。）
因此，您刚刚充分证明了为什么冒泡排序不适用于大型数据集，而 100,000 个项目足以证明这一点。
于 2009-06-15T20:02:54.943 回答
2
我认为在如此大的数据集上使用气泡基本上是在浪费时间。速度慢的原因有3个：
1) Python 很慢 2) 冒泡排序很慢 3) 列出的冒泡排序编码不正确/效率低下。
不管怎么编码，都是O(N^2)。为什么不使用合并/树排序..或者如果您想尝试快速排序（也是最坏情况 O(N^2)），对于您的特定数据集可能会更快。如果数据中已经有很多排序，我相信快速排序在经验上会更快。
于 2009-06-15T19:43:36.857 回答
2
随着输入中元素数量的增加，冒泡排序通常不能很好地扩展到大多数可能的输入。（即，它是 O(N^2)。）
随着 N 的增长，给定一个大小为 N 的随机输入数组，您不太可能得到一个使用冒泡排序快速排序的数组（例如，几乎排序的数组）。你更有可能得到一个需要很长时间才能排序的数组。
但是，这里真正的问题是您发布的代码不是冒泡排序。传统上，如果没有进行交换并且不尝试交换已经排序的值，则冒泡排序将提前终止。（经过 P 次通过后，最后 P 项将按正确顺序排列，因此您无需处理它们。）实际发布的代码将始终检查数组中的每一对，因此它将始终运行内部循环N^2次。对于 100000 个元素，即 10000000000 次迭代。
于 2009-06-15T19:45:08.897 回答
2
一方面，你做了太多的循环。您的内部循环应该从 i + 1 到列表的末尾，而不是从 0。其次，正如其他人所指出的，冒泡排序具有 O(N^2) 复杂性，因此对于 100000 个元素，您将循环 10,000,000,000 次。更糟糕的是，循环是解释语言性能最差的领域之一。这一切都导致了令人难以置信的糟糕表现。这就是为什么任何需要如此紧密循环的计算通常都用 C/C++ 编写并包装以供 Python 等语言使用。
于 2009-06-15T18:33:27.003 回答
2
这里我整理了一些代码来比较基本冒泡排序和更简化的版本（基本与修改） - 修改后的速度大约快 2-3 倍，仍然是慢速排序，但速度更快
from array import *
from random import *
from time import *
def randarray(typecode, numElements, minValue, maxValue):
a = array(typecode)
for i in xrange(0, numElements):
a.append(randint(minValue, maxValue))
return a
def basesort(l):
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]
return l
def modifiedsort(l):
NotComplete = True
i = 0
arange = xrange(len(l))
while NotComplete:
NotComplete = False
for j in xrange(len(l) - i):
if l[i]<l[j]:
l[i], l[j] = l[j], l[i]
NotComplete = True
i += 1
Num = 1000
b = randarray('i', Num, 1, 100000)
m = b[:]
print 'perform base bubble sort'
t = time()
basesort(b)
basetime = time() - t
print basetime
#print a
print 'complete'
print 'perform modified bubble sort'
t = time()
modifiedsort(m)
modtime = time() - t
print modtime
#print a
print 'complete'
print 'mod sort is ', basetime / modtime,' fast then base sort'
于 2009-06-15T19:28:22.830 回答
1
因为它将执行比较并且可能交换 100,000 x 100,000 次。如果计算机的速度足以每秒执行最里面的语句 1,000,000 次，那仍然是 167 分钟，略短于 3 小时。
顺便说一句，为什么有这么多关于 SO 的愚蠢问题？不会做简单代数不是编程的先决条件吗？;-)
于 2009-06-15T18:53:53.587 回答
1
首先，出于本回复的目的，我假设-因为您自己声明-您这样做只是为了对不同的语言进行基准测试。所以我不会进入“冒泡排序只是缓慢”的领域。真正的问题是为什么它在 Python 中要慢得多。
答案是 Python 本质上比 C++ 甚至 Java 慢得多。您在典型的事件驱动或 I/O 绑定应用程序中看不到它，因为大部分时间要么在等待输入时处于空闲状态，要么在等待 I/O 调用完成。但是，在您的情况下，该算法完全受 CPU 限制，因此您直接测量 Python 字节码解释器的性能。据估计，这比执行相应的本机代码慢 20-30 倍，这在 C++ 和 Java 中都是如此。
一般来说，任何时候你在 Python 中编写一个长时间运行的 CPU 密集型循环，你都应该期待这种性能。解决此问题的唯一方法是将整个循环移动到 C 中。仅移动主体（例如使用 NumPy）对您没有多大帮助，因为循环迭代本身仍将由 Python 解释器执行。
于 2009-06-15T21:01:04.547 回答
1
如果您有兴趣制作自己的排序，只需几行代码即可将冒泡排序更改为梳状排序。梳排序几乎和最好的排序一样好。当然，制作自己的排序最好作为学习练习。
梳状排序在冒泡排序的基础上进行了改进，并且在速度上可以与更复杂的算法（如快速排序）相媲美。
于 2009-06-15T17:30:51.637 回答
1
对我来说，这看起来不像冒泡排序，如果是，那么它的实现效率非常低。
于 2009-06-15T17:32:05.660 回答
0
You can do
l.reverse()
Script ee.py:
l = []
for i in xrange(100000):
l.append(i)
l.reverse()
lyrae@localhost:~/Desktop$ time python ee.py
real 0m0.047s
user 0m0.044s
sys 0m0.004s
于 2009-06-15T20:25:56.550 回答
0
如果您必须编写自己的代码，请使用插入排序。它的代码量大致相同，但速度要快几倍。
于 2009-06-15T18:24:39.140 回答
0
我忘了补充，如果您对数据集的大小和键的分布有所了解，那么您可以使用 O(N) 的基数排序。要了解基数排序的概念，请考虑您对数字或多或少分布在 0、100,000 之间进行排序的情况。然后你只需创建类似于哈希表的东西，比如一个包含 100,000 个列表的数组，然后将每个数字添加到存储桶中。这是我在几分钟内编写的一个实现，它生成一些随机数据，对其进行排序，然后打印出一个随机段。100,000 个整数数组的执行时间不到 1 秒。
Option Strict On 选项显式打开
模块模块1
Private Const MAX_SIZE As Integer = 100000
Private m_input(MAX_SIZE) As Integer
Private m_table(MAX_SIZE) As List(Of Integer)
Private m_randomGen As New Random()
Private m_operations As Integer = 0
Private Sub generateData()
' fill with random numbers between 0 and MAX_SIZE - 1
For i = 0 To MAX_SIZE - 1
m_input(i) = m_randomGen.Next(0, MAX_SIZE - 1)
Next
End Sub
Private Sub sortData()
For i As Integer = 0 To MAX_SIZE - 1
Dim x = m_input(i)
If m_table(x) Is Nothing Then
m_table(x) = New List(Of Integer)
End If
m_table(x).Add(x)
' clearly this is simply going to be MAX_SIZE -1
m_operations = m_operations + 1
Next
End Sub
Private Sub printData(ByVal start As Integer, ByVal finish As Integer)
If start < 0 Or start > MAX_SIZE - 1 Then
Throw New Exception("printData - start out of range")
End If
If finish < 0 Or finish > MAX_SIZE - 1 Then
Throw New Exception("printData - finish out of range")
End If
For i As Integer = start To finish
If m_table(i) IsNot Nothing Then
For Each x In m_table(i)
Console.WriteLine(x)
Next
End If
Next
End Sub
' run the entire sort, but just print out the first 100 for verification purposes
Private Sub test()
m_operations = 0
generateData()
Console.WriteLine("Time started = " & Now.ToString())
sortData()
Console.WriteLine("Time finished = " & Now.ToString & " Number of operations = " & m_operations.ToString())
' print out a random 100 segment from the sorted array
Dim start As Integer = m_randomGen.Next(0, MAX_SIZE - 101)
printData(start, start + 100)
End Sub
Sub Main()
test()
Console.ReadLine()
End Sub
结束模块 开始时间 = 2009 年 6 月 15 日下午 4:04:08 完成时间 = 2009 年 6 月 15 日下午 4:04:08 操作次数 = 100000 21429 21430 21430 21431 21431 21432 21433 21435 21435 21435 21436 21435 21436 2435 21436 2349 21436 2341 ...
于 2009-06-15T20:06:50.477 回答
0
就像其他帖子所说的那样，冒泡排序很可怕。由于性能不佳，几乎应该不惜一切代价避免这种情况，就像您正在经历的那样。
幸运的是，还有很多其他的排序算法，例如http://en.wikipedia.org/wiki/Sorting_algorithm。
根据我在学校的经验，快速排序和归并排序是在冒泡排序之后或不久之后引入的另外两种基本排序算法。所以我建议你研究那些学习更有效的排序方法。
于 2009-06-15T17:36:01.897 回答