在 Python 中排序的最快方法
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/3855537/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Fastest way to sort in Python
提问by Anders
What is the fastest way to sort an array of whole integers bigger than 0 and less than 100000 in Python? But not using the built in functions like sort.
在 Python 中对大于 0 且小于 100000 的整数数组进行排序的最快方法是什么？但不使用像 sort 这样的内置函数。
Im looking at the possibility to combine 2 sport functions depending on input size.
我正在考虑根据输入大小组合 2 项运动功能的可能性。
采纳答案by fmark
If you are interested in asymptotic time, then counting sort or radix sort provide good performance.
如果您对渐近时间感兴趣，那么计数排序或基数排序会提供良好的性能。
However, if you are interested in wall clock timeyou will need to compare performance between different algorithms using your particular data sets, as different algorithms perform differently with different datasets. In that case, its always worth trying quicksort:
但是，如果您对挂钟时间感兴趣，则需要使用特定数据集比较不同算法之间的性能，因为不同算法对不同数据集的性能不同。在这种情况下，它总是值得尝试快速排序：
def qsort(inlist):
if inlist == []:
return []
else:
pivot = inlist[0]
lesser = qsort([x for x in inlist[1:] if x < pivot])
greater = qsort([x for x in inlist[1:] if x >= pivot])
return lesser + [pivot] + greater
Source: http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Python
来源：http: //rosettacode.org/wiki/Sorting_algorithms/Quicksort#Python
回答by codaddict
Since you know the range of numbers, you can use Counting Sortwhich will be linear in time.
由于您知道数字的范围，因此您可以使用时间线性的计数排序。
回答by Hannesh
The built in functions are best, but since you can't use them have a look at this:
内置函数是最好的，但既然你不能使用它们，看看这个：
回答by Tauquir
Early versions of Python used a hybrid of samplesort(a variant of quicksort with large sample size) and binary insertion sort as the built-in sorting algorithm. This proved to be somewhat unstable. S0, from python 2.3 onward uses adaptive mergesortalgorithm.
Python 的早期版本使用混合samplesort（具有大样本量的快速排序的变体）和二进制插入排序作为内置排序算法。这被证明有些不稳定。S0，从 python 2.3 开始使用adaptive mergesort算法。
Order of mergesort (average) = O(nlogn).
Order of mergesort (worst) = O(nlogn).
But Order of quick sort (worst) = n*2
归并排序的顺序（平均）= O(nlogn). 归并排序（最差）= O(nlogn). 但是快速排序的顺序（最差）= n*2
if you uses list=[ .............. ]
如果你使用 list=[ .............. ]
list.sort()uses mergesort algorithm.
list.sort()用途 mergesort algorithm.
For comparison between sorting algorithm you can read wiki
对于排序算法之间的比较，您可以阅读wiki
For detail comparison comp
详细比较comp
回答by Rajan
We can use count sort using a dictionary to minimize the additional space usage, and keep the running time low as well. The count sort is much slower for small sizes of the input array because of the python vs C implementation overhead. The count sort starts to overtake the regular sort when the size of the array (COUNT) is about 1 million.
我们可以使用字典使用计数排序来最小化额外的空间使用，并保持较低的运行时间。由于 python 与 C 实现的开销，对于小尺寸的输入数组，计数排序要慢得多。当数组的大小（COUNT）大约为 100 万时，计数排序开始超过常规排序。
If you really want huge speedups for smaller size inputs, implement the count sort in C and call it from Python.
如果您真的希望对较小尺寸的输入进行大幅加速，请在 C 中实现计数排序并从 Python 中调用它。
(Fixed a bug which Aaron (+1) helped catch ...) The python only implementation below compares the 2 approaches...
（修复了 Aaron (+1) 帮助捕获的错误......）下面的 Python only 实现比较了 2 种方法......
import random
import time
COUNT = 3000000
array = [random.randint(1,100000) for i in range(COUNT)]
random.shuffle(array)
array1 = array[:]
start = time.time()
array1.sort()
end = time.time()
time1 = (end-start)
print 'Time to sort = ', time1*1000, 'ms'
array2 = array[:]
start = time.time()
ardict = {}
for a in array2:
try:
ardict[a] += 1
except:
ardict[a] = 1
indx = 0
for a in sorted(ardict.keys()):
b = ardict[a]
array2[indx:indx+b] = [a for i in xrange(b)]
indx += b
end = time.time()
time2 = (end-start)
print 'Time to count sort = ', time2*1000, 'ms'
print 'Ratio =', time2/time1
回答by Magnus
Radix sort theoretically runs in linear time (sort time grows roughly in direct proportion to array size ), but in practice Quicksort is probably more suited, unless you're sorting absolutely massive arrays.
基数排序理论上以线性时间运行（排序时间大致与数组大小成正比），但实际上快速排序可能更适合，除非您对绝对庞大的数组进行排序。
If you want to make quicksort a bit faster, you can use insertion sort] when the array size becomes small.
如果你想让quicksort快一点，你可以在数组变小的时候使用插入排序]。
It would probably be helpful to understand the concepts of algorithmic complexity and Big-O notation too.
理解算法复杂性和大 O 符号的概念也可能会有所帮助。
回答by user2812083
def sort(l):
p = 0
while(p<len(l)-1):
if(l[p]>l[p+1]):
l[p],l[p+1] = l[p+1],l[p]
if(not(p==0)):
p = p-1
else:
p += 1
return l
this is a algorithm that I created but is really fast. just do sort(l) l being the list that you want to sort.
这是我创建的算法，但速度非常快。只是做 sort(l) l 是你想要排序的列表。
回答by asdf
@fmark Some benchmarking of a python merge-sort implementation I wrote against python quicksorts from http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Pythonand from top answer.
@fmark 我针对来自http://rosettacode.org/wiki/Sorting_algorithms/Quicksort#Python和顶级答案的python 快速排序编写的 python 合并排序实现的一些基准测试。
- Size of the list and size of numbers in list irrelevant
- 列表的大小和列表中数字的大小无关
merge sort wins, however it uses builtin int() to floor
合并排序获胜，但是它使用内置的 int() 来进行排序
import numpy as np
x = list(np.random.rand(100))
# TEST 1, merge_sort
def merge(l, p, q, r):
n1 = q - p + 1
n2 = r - q
left = l[p : p + n1]
right = l[q + 1 : q + 1 + n2]
i = 0
j = 0
k = p
while k < r + 1:
if i == n1:
l[k] = right[j]
j += 1
elif j == n2:
l[k] = left[i]
i += 1
elif left[i] <= right[j]:
l[k] = left[i]
i += 1
else:
l[k] = right[j]
j += 1
k += 1
def _merge_sort(l, p, r):
if p < r:
q = int((p + r)/2)
_merge_sort(l, p, q)
_merge_sort(l, q+1, r)
merge(l, p, q, r)
def merge_sort(l):
_merge_sort(l, 0, len(l)-1)
# TEST 2
def quicksort(array):
_quicksort(array, 0, len(array) - 1)
def _quicksort(array, start, stop):
if stop - start > 0:
pivot, left, right = array[start], start, stop
while left <= right:
while array[left] < pivot:
left += 1
while array[right] > pivot:
right -= 1
if left <= right:
array[left], array[right] = array[right], array[left]
left += 1
right -= 1
_quicksort(array, start, right)
_quicksort(array, left, stop)
# TEST 3
def qsort(inlist):
if inlist == []:
return []
else:
pivot = inlist[0]
lesser = qsort([x for x in inlist[1:] if x < pivot])
greater = qsort([x for x in inlist[1:] if x >= pivot])
return lesser + [pivot] + greater
def test1():
merge_sort(x)
def test2():
quicksort(x)
def test3():
qsort(x)
if __name__ == '__main__':
import timeit
print('merge_sort:', timeit.timeit("test1()", setup="from __main__ import test1, x;", number=10000))
print('quicksort:', timeit.timeit("test2()", setup="from __main__ import test2, x;", number=10000))
print('qsort:', timeit.timeit("test3()", setup="from __main__ import test3, x;", number=10000))
回答by Marek
I might be a little late to the show, but there's an interesting article that compares different sorts at https://www.linkedin.com/pulse/sorting-efficiently-python-lakshmi-prakash
我的节目可能有点晚了，但是有一篇有趣的文章比较了https://www.linkedin.com/pulse/sorting-efficiently-python-lakshmi-prakash
One of the main takeaways is that while the default sort does great we can do a little better with a compiled version of quicksort. This requires the Numba package.
主要的收获之一是，虽然默认排序效果很好，但我们可以使用快速排序的编译版本做得更好。这需要 Numba 包。
Here's a link to the Github repo: https://github.com/lprakash/Sorting-Algorithms/blob/master/sorts.ipynb
这是 Github 存储库的链接：https: //github.com/lprakash/Sorting-Algorithms/blob/master/sorts.ipynb
