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

2014-05-01 10:23:12 +08:00
 wuxqing
数据结构：
[[1, 111], [2, 201], [3, 211], [4, 111], [5, 201], ...]
第一个值是连续的，int32类型
第二个数是有重复的，int16类型
根据第二个值进行排序
数据量在1000万

想不到好思路
3798 次点击
所在节点    问与答
7 条回复
yangff
2014-05-01 10:33:43 +08:00
1kW快排就行了。i7的话大概1～2秒就出来了吧。
wlxiong
2014-05-01 10:38:05 +08:00
1) 因为第二个值是int16那么最多64*1024种数值 可以考虑建一个类似hash array的结构 可以做到 O(n)
2) 或者考虑做radix sort
66CCFF
2014-05-01 13:47:27 +08:00
第二个元素int16的话，用桶排吧。
0~65535做桶，每个桶拉一个链下去存第一个元素，O(1)插入。参考链式前向星。
复杂度O(n)
riaqn
2014-05-01 13:52:08 +08:00
同意楼上
wuxqing
2014-05-04 10:31:11 +08:00
@yangff 是低端安卓设备上用，快排速度不行
wuxqing
2014-05-04 10:33:40 +08:00
@wlxiong 不知道第二个值对应有多少ID，hash array不好处理
wuxqing
2014-05-04 10:35:01 +08:00
@66CCFF 桶排在用，由于设备比较低端，性能还是差了些

这是一个专为移动设备优化的页面（即为了让你能够在 Google 搜索结果里秒开这个页面），如果你希望参与 V2EX 社区的讨论，你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/110731

V2EX 是创意工作者们的社区，是一个分享自己正在做的有趣事物、交流想法，可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX