Java 位圖排序法原理與效能實測深度解析

位圖排序核心思想

位圖排序利用位元陣列映射整數存在性：每個 bit 對應一個整數，1 表示存在，0 表示不存在。適用於已知範圍、無重複或可計數重複、資料密集的整數排序場景，時間複雜度 O(n + k)，空間複雜度 O(k)，k 為最大值範圍。

基本版實作（無重複整數）

import java.util.*;

public class BitmapUniqueSort {
    private static final int MAX_VALUE = 1_000_000;
    private static final int[] bitmap = new int[MAX_VALUE + 1];
    private static final List<Integer> result = new ArrayList<>();

    public static List<Integer> sort(List<Integer> input) {
        // 重置位圖
        Arrays.fill(bitmap, 0);
        result.clear();

        // 標記存在的數字
        for (int num : input) {
            if (num >= 0 && num <= MAX_VALUE) {
                bitmap[num] = 1;
            }
        }

        // 遍歷輸出有序結果
        for (int i = 0; i <= MAX_VALUE; i++) {
            if (bitmap[i] == 1) {
                result.add(i);
            }
        }
        return result;
    }

    public static void main(String[] args) {
        List<Integer> data = new ArrayList<>();
        for (int i = 1; i <= 1_000_000; i++) data.add(i);
        Collections.shuffle(data);

        long start = System.nanoTime();
        Collections.sort(data);
        System.out.println("Java 內建排序: " + (System.nanoTime() - start) + " ns");

        Collections.shuffle(data);
        start = System.nanoTime();
        sort(data);
        System.out.println("位圖排序: " + (System.nanoTime() - start) + " ns");
    }
}

進階版實作（支援重複整數計數）

public class BitmapDuplicateSort {
    public static List<Integer> sort(List<Integer> input, int maxValue) {
        int[] countArray = new int[maxValue + 1];
        List<Integer> result = new ArrayList<>();

        for (int num : input) {
            if (num >= 0 && num <= maxValue) {
                countArray[num]++;
            }
        }

        for (int i = 0; i <= maxValue; i++) {
            for (int c = 0; c < countArray[i]; c++) {
                result.add(i);
            }
        }
        return result;
    }
}

效能實測數據對比

適用條件與限制分析

記憶體優化技巧

1. 使用 BitSet 替代 int[]：Java 內建 java.util.BitSet 更節省記憶體，自動擴容
2. 分塊處理：大範圍分段排序，配合外部排序合併
3. 壓縮位圖：RoaringBitmap、EWAH 等壓縮算法處理稀疏資料

// BitSet 版本
BitSet bitmap = new BitSet(MAX_VALUE + 1);
for (int num : input) bitmap.set(num);
for (int i = bitmap.nextSetBit(0); i >= 0; i = bitmap.nextSetBit(i + 1)) {
    result.add(i);
}

實戰應用案例

• 電信去重：手機號碼 11 位數，前 7 位固定，後 4 位 0000-9999，位圖僅需 10,000 bits (1.25 KB)
• 大數據 ID 排序：64 位 ID 取低 32 位分桶，桶內位圖排序
• 權限系統：用戶 ID 位圖表示在線/權限狀態，O(1) 查詢

總結

位圖排序以空間換時間，在密集整數、已知範圍場景下展現數量級效能優勢。Java 開發者可直接使用 BitSet 或成熟庫 RoaringBitmap 避免重複造輪子。關鍵在於評估資料特徵：密集用位圖，稀疏用哈希/樹結構，通用場景信任 JDK TimSort。