大数据量排序有没有非常快的算法？

This topic created in 4578 days ago, the information mentioned may be changed or developed.

数据结构：
[[1, 111], [2, 201], [3, 211], [4, 111], [5, 201], ...]
第一个值是连续的，int32类型
第二个数是有重复的，int16类型
根据第二个值进行排序
数据量在1000万

想不到好思路

7 replies • 2014-05-04 10:35:01 +08:00

yangff

May 1, 2014

1kW快排就行了。i7的话大概1～2秒就出来了吧。

wlxiong

May 1, 2014 via Android

1) 因为第二个值是int16那么最多64*1024种数值可以考虑建一个类似hash array的结构可以做到 O(n)
2) 或者考虑做radix sort

66CCFF

May 1, 2014

第二个元素int16的话，用桶排吧。
0~65535做桶，每个桶拉一个链下去存第一个元素，O(1)插入。参考链式前向星。
复杂度O(n)

riaqn

May 1, 2014 via iPhone

同意楼上

wuxqing

May 4, 2014

@yangff 是低端安卓设备上用，快排速度不行

wuxqing

May 4, 2014

@wlxiong 不知道第二个值对应有多少ID，hash array不好处理

wuxqing

May 4, 2014