位图排序

十大经典排序算法

位图排序（Bitmap Sort）也称为 bitmap 排序，它主要用于海量数据去重，去重之后还可以再排序。位图排序的原理和计数排序类似，一个二进制位相当于一个桶，但不同的是位图排序中一个二进制位最多只能存放一个值，所以位图排序中不能有重复的元素，如果有重复的会被覆盖，导致结果错误。可以参照 计数排序 ，数组中最小的值放到 bitmap[0] 的二进制位右边第一个位置，这里还要注意负数的处理。

代码如下：

    private void bitmapSort(int[] nums) {
        int max = Arrays.stream(nums).max().getAsInt();// 获取数组中的最大值
        int min = Arrays.stream(nums).min().getAsInt();// 获取数组中的最小值
        // max和min的差值不能太大，否则运算的时候出现溢出导致结果错误。
        int length = (max - min) / 64 + 1;// 数组的长度。
        long[] bitmap = new long[length];
        // 把数字放到对应的二进制位中，防止出现负数，所以每个数字都要减去最小值min。
        for (int i = 0; i < nums.length; i++)
            bitmap[(nums[i] - min) / 64] |= 1L << ((nums[i] - min) % 64);
        int index = 0;
        // 从二进制位中取出数字。
        for (int i = 0; i < length; i++)
            for (int j = 0; j < 64; j++)
                if ((bitmap[i] & (1L << j)) != 0) // 判断当前位是否有数字。
                    nums[index++] = i * 64 + j + min;
    }

相关链接