AC. 梦想

frank_c1

线性排序小技巧

发布于2016年02月07日 | 暂无评论 | 1,339阅读 | 基础

在回老家的路上,关于排序这个问题突然想到一个有趣的做法。

先来看一道入门题:

给定长度为n的整数数组A,将元素从小到大排序。1 \le n \le 10 ^ 6,0 \le A_i \le 10 ^ 6,时限1s。

非常简单,由于数据范围较小,直接桶排即可。

再来看一道加强版:

给定长度为n的整数数组A,将元素从小到大排序。1 \le n \le 10 ^ 6,0 \le A_i \le 10 ^ 9,时限1s。

数据范围大了怎么办?数组开不下,桶排序不灵了?实际上,还是可以用桶排序来做,不过要稍微变换一下。从二进制上看,我们把每个元素拆成两个16位整数,问题也就变成以高16位整数为第一关键字,低16位整数为第二关键字的排序。由于16位整数最大不超过65535,所以又可以用桶排啦。虽然常数比原版桶排大,但在较大数据范围下比快速排序要快。另外,该算法需要接近4倍空间。

或许这个技巧早已有很多人发现了,希望我不是最后一个知道的吧。

[UPD] 上述一些排序的名称我不是很确定,大家只需意会即可。