请教一种大量数据的快速排序的方法

Question

目前我有大量的数据（5万左右），比如（32，3，4，2，34，5466，223，45。。。）
我想请教一种能够快速排序的方法。 目前尝试过了 quicksort（快速排序） 和 mergesort（归并排序）， mergesort 的排序更快一些，但是速度还不是很理想。 请问有没有比 mergesor 更加快的排序方法？

万分感谢

Answer 1

切分到多台机器上排序，然后做n-way merge。
不过5万这种量还真犯不上这么麻烦。

基于比较的排序，其时间复杂的理论下限是O(N*log(N))，常见的quick sort、heap sort、merge sort都在此列，所以你就不要在这个事情上再浪费时间了。
如果数字本身有一定特征，比如都是[n1, n2]区间内的整数，你可以用基数排序、桶排序之类不基于比较的算法，它们的时间复杂度可以低至O(N)，但是空间复杂度至少是O(N)。

Answer 2

5w也叫大数据。。。。
quick sort 一眨眼就排序好了

Answer 3

5w的大数据...

数据量太小, 排序算法除了时间复杂度, 也需要考虑常系数. 试试希尔排序吧.

Answer 4

记得快速排序的平均时间复杂度是 nlog(n）,你可以进行一次快速排序以后，两个线程处理，然后再快排一次，四个线程处理。。。或者你可以处理一下你的 key 值，尽量让左右两边的个数相等，时间复杂度达到 nlogn。要么就堆排序，最坏情况也是 nlogn.我能想到的，希望能有帮助。

Answer 5

看一下每个元素的范围，如果幅度不是很大，可以考虑桶排序（我这边是这么叫的）
号称是 O(n) 的时间复杂度
另外我想了解你一下你所用的语言？我是从你另外一个帖子里找过来的，感觉你学的都是面向应用的语言，这些语言在速度上本身不具有太大的优势。
一般这种大数据排序的任务会交给后端，后端一般使用高效的语言，排个5W的数据毫无压力。

Answer 6

quicksort+random+小规模冒泡+三路划分。

Answer 7

１.5W数据不算大。快排原地排序很快。O(nlogn)的时间复杂度。不需要额外空间，是最合适的。
２.要更快，可以考虑基数排序，前提是数据的范围是已知的。时间复杂度是O(n)。需要额外空间。
３.数据如果是无重复且范围已知，可采用bitmap，速度非常快。

Answer 8

5W算不上大数据
5W做快排的时间还是很轻松的，你觉得慢可能是实现不大好。5W行的数据在shell里直接用个sort很是很轻松的，如果是编程排的话，任何语言内建的排序都不会太慢。
也可能是遇到快排的最差情况，可以通过随机化办法来优化，让快排不容易跌入最差情况

如果你的数据量大，但是数据范围很小，可以使用统计排序（也称为“桶排序”）或者基数排序

Answer 9

如果本身就有序的情况下，时间复杂度会降到O(n^2)

Answer 10

5万数据也算大？

好吧，如果你的数据本身数字不是很大，只是数据量大的话，可以试试桶排。拿下标作答。复杂度是 O(MAXN)，MAXN指的是你最大的那个数字大小。

for(int i = 0; i < n; i++)
{
    sort[arr[i]]++;
}

for(int i = 0; i < MAXN; i++)
{
    for(int j = 0; j < sort[i]; j++)
    {
        printf("%d ", i);
    }
}

Answer 11

5W的数据太少了，我这20W的数据用快速排序也一会儿就好了