位图排序：对随机生成的一亿数字进行排序（排序时间控制在3秒内）

位图排序是一种效率极高(复杂度可达O(n))并且很节省空间的一种排序方法，特点是用内存空间换取CPU时间。
其原理是将一个bit当作一个数字，然后遍历，设置1为存在，0为不存在，然后顺序输出即可。
例如：
有一个集合{4,6,5,8,2,1}，我们可以用一个8位的二进制向量set[1-8]来表示该集合，如果数据存在，则将set相对应的二进制位置1，否则置0.根据给出的集合得到的set为{1,1,0,1,1,1,0,1}，然后再根据set集合的值是否为1输出对应的下标即可得到集合{1,2,4,5,6,8}。

我本来打算使用位图排序来完成

// 对1亿个随机数字进行排序（3秒）
    public static int[] getBitMap(int[] intArray) {
        // 获取数字数组的最大值
        int maxValue = intArray[0];
        for (int i = 0; i < intArray.length; ++i) {
            if (maxValue < intArray[i]) {
                maxValue = intArray[i];
            }
        }
        // 设置位图数组bitMap的长度（位图数组长度 = 数字数组.maxValue + 1）
        byte[] bitmap = new byte[maxValue + 1];
        // 将数组转化为位图数组
        for (int i = 0; i < intArray.length; ++i) {
            int value = intArray[i];
            bitmap[value] = 1;
        }

        // 进行排序（倒序）
        int[] result = new int[intArray.length];
        int index = 0;
        for (int i = maxValue; i >= 0 & index < result.length; i--) {
            if (bitmap[i] == 1) {
                result[index++] = i;
            }
        }
        return result;
    }


    public static void main(String[] args) {

        // 设置数组长度
        int[] intArray = new int[100000000];
        Random random = new Random();
        for (int i = 0; i < intArray.length; ++i) {
            // 随机生成数字
            intArray[i] = (int) (Math.random() * intArray.length);
        }
        // 测试时间
        System.out.println("Sort begin...");
        // 开始时间
        long current = System.currentTimeMillis();
        int[] result = Sort.getBitMap(intArray);
        //结束时间
        System.out.println("排序时间" + (System.currentTimeMillis() - current) + "ms");
        System.out.println("Sort end...");
//        for (int i = 0; i < result.length; ++i) {
//            System.out.print(result[i] + ",");
//        }

但是这种排序方法对输入的数据是有比较严格的要求：
1.数据不能重复
2.大致知道数据的范围

当数据有重复时，排序就会出错（重复的数字都指向同一个“1”，所以最后只有“第一个”才能正确表示，其它都会变为默认值0）

26430876-30853741c1169cf6.jpg image

所以这种排序算法用在这感觉不太合适，大量数据排序好像都是通过将其拆分为很多小部分进行排序，然后最终在合并成一个排好序的整体。
这里想问一下，这个问题有没有很好的解决方法啊。。。