15行代码5秒搞定上亿规模整数排序

年末大家闲的蛋疼，有同事抛出一个题目切磋切磋。

给定一个包含有一亿随机整数的数组，要求对其排序，越快越好，请给出算法。（随意发挥，对内存无要求）

之后一哥们给出一个大规模数据排序的Fork/Join解法，基本思路如下：“从样本中任意取一个元素（比如最后一个元素），将整个数组Array分为两部分Array_1和Array_2，其中Array_1的每个元素比这个数大，Array_2的每个元素比这个数小”，再分别对Array_1和Array_2执行上述操作，直到每个小array_n_n的规模到达某个量级（比如5k个），再用基本的排序算法对每个小array_n_n排序，最后合并整个结果集。

经测试，别说亿级，即使样本规模缩小到百万级，此解法的效率也是极其低下，当然这不是Map/Reduce擅长的场景，不是他的菜，我们只是玩玩，切磋切磋而已。

后来我想到一个自以为比较不错的方法，记录下来以备用。当然此法也是有缺陷的，稍后再说，思路如下：不好意思，拿铁道部举个例子，假设样本数组中的数值表示的是某人回家的火车的车次编码，比如第一个元素是302，其代表这个人要坐302次列车回家见妈，这一亿个样本数据就是一亿个人，每个人背上写着回家要坐的火车车次号码编码（不是座位号，仅仅是哪趟车），比如你是1404次列车，他是302次列车，我也是1404次，首先请铁道部车准备好一亿辆从小到大编好号码的火车（艾玛，铁道部赚大了），1次，2次。。302次。。。1404次一字排开，然后大家按队伍先后一个个上火车（当然也可以一股脑往上挤，那就是并发啦），最后铁道部按照火车次序挨个说，你们都是使用插件抢的票，统统下车，这按照火车次序挨个清理出来的人即是排序结果。

大家都是码农，就直接上代码： 

@Test
public void sort() {
  final byte[] tmp = new byte[SIZE];// 用byte省点空间
  int index = SIZE;
  while (--index >= 0) {
    tmp[datas[index]] += 1;
  }
  byte t;
  int i = 0;
  index = SIZE;
  while (--index >= 0) {
    t = tmp[index];
    while (t-- > 0)
      datas[i++] = index;
  }
}

上述代码算头算尾一共15行，没错吧，我不是标题党！我在公司机器上（32位 win server 2003 3G内存 2核CPU）跑基本在5.5秒左右即可完成排序，回家在自己机器上（64位win7旗舰版 4核CPU 4G内存）试了很多遍，基本都是在4.5秒左右便可以完成。

当然，这算法是有缺陷的，辅助数组byte[] tmp的初始程度应该是样本数据中的绝对值的最大值，你必须先想办法弄到最大值，额。。。如果你是高富帅可以new个Integer.MAX_VALUE的辅助数组。另外，有同事说你这个算法要求样本必须是正数才行，我觉得包含负数也OK啊，再弄个byte[] tmp2，针对负数取绝对值反着排，分而治之再合并。代码见附件，欢迎拍砖。

unit test

ps：首先，我承认我是标题党，我就是为了引起大家注意的，谁让咱刚开始写博客，人气低呢。

评论