如何在不使用排序函数的情况下对python中的1000万个数字进行排序

Question

在python中，在不使用内置函数的情况下，对随机生成的1到100之间的1000万个数字的列表进行排序，Quicksort在这里对我不起作用。

我使用了上述链接中的快速排序代码：http://interactivepython.org/runestone/static/pythonds/SortSearch/TheQuickSort.html

实现时出错：对于范围(0，100000(内的x：listOfNumbers.append(random.randint(1100((

quickSort(数字列表(打印(数字列表(

运行时错误：超过的最大递归深度

Answer 1

您可以使用任何您想要的排序算法，只要您正确地实现它。但问题是需要基数排序。特别是最愚蠢的基数排序，桶计数器。

您有N=10,000,000总值和一系列M=100不同值。桶计数器将占用比O(N*log N)更好的O(N+M)时间和可忽略不计的O(M)空间。最棒的是，它非常简单：

def bucketsorted100(xs):
buckets = [0] * 101
for x in xs:
buckets[x] += 1
for x, count in enumerate(buckets):
yield from [x] * count

很明显，你可以将其扩展为不为1-100的数字进行硬编码(实际上，我为0-100的数字进行了硬编码，浪费了1%的空间，但谁在乎呢？(。或者，您可以添加对key函数的支持。或者，您可以使用Counter而不是list来简化它。

---

_{1。从技术上讲，它是O(logN * M)空间，因为计数范围高达N，需要logN位，而值范围仅高达100，需要恒定数量的位。但实际上，在CPython中，所有计数都适合一个30位的"数字"，因此logN因子永远不会出现}

Answer 2

您可以使用强大的Bogosort。

import random
def is_sorted(data):
for i in range(len(data) - 1):
if data[i] > data[i + 1]:
return False
return True
def bogosort(data):
while not is_sorted(data):
random.shuffle(data)
return data

Answer 3

也许numpy会更快。。。您可以将数字转换为numpy array，然后使用numpy.sort

像这样：

import numpy as np
mylist=[15,65,3,1,10,35,11,65,23,95,20,36,85,12,37,85,46,93] # ...
sorted_mylist=np.ndarray.tolist(np.sort(np.asarray(mylist)))
print sorted_mylist

给你的是：

[1, 3, 10, 11, 12, 15, 20, 23, 35, 36, 37, 46, 65, 65, 85, 85, 93, 95]