位图排序是利用数组下标表示数值、值表示存在性的去重有序枚举方法；时间复杂度O(n+m)，空间复杂度O(m)；Java中可用boolean[]或long[]实现，适合最大值几百万以内的正整数。
位图排序不是传统意义上的“排序算法”，而是利用数组（或布尔数组）的下标作为数值、值作为存在标记，实现对不重复正整数的去重 + 有序枚举。它本质是空间换时间：时间复杂度 O(n + m)，其中 m 是数据最大值；空间复杂度 O(m)。Java 中可用 boolean[] 或更省内存的 long[]（按位操作）实现。
用 boolean[] 实现简洁版位图（适合中小范围）
适用于最大值在几百万以内（如 0～10⁶），内存充足且追求代码清晰。
- 创建长度为
maxValue + 1的boolean[] bitmap，初始全false - 遍历输入数组，对每个正整数
x，执行bitmap[x] = true（自动去重） - 从下标
1开始遍历bitmap，遇到true就输出下标——结果天然升序
示例：
java-api-doc-generator
下载
分析 Java Spring Boot 后端 Controller 代码，自动生成 Markdown 格式的接口文档。当用户说“生成 Java 接口文档”、“生成 API 文档”、“从 Spring 代码生成文档”时触发。
int max = Arrays.stream(nums).max().orElse(0);
boolean[] map = new boolean[max + 1];
for (int x : nums) if (x > 0) map[x] = true;
for (int i = 1; i // 输出：1 2 3 4 5 6 9
用 long[] 实现紧凑位图（节省 64 倍空间）
当最大值达千万甚至亿级时，boolean[] 占用过大（如 1 亿个 boolean ≈ 100MB）。改用 long[]，每个 long 存 64 位，用位运算标记。
- 计算所需 long 数量：
size = (maxValue + 63) / 64 - 标记数字 x：取
index = x / 64，位偏移bit = x % 64，执行bits[index] |= (1L - 查询 x 是否存在：检查
(bits[index] & (1L - 枚举时双重循环：外层遍历
long元素，内层用Long.bitCount()或逐位检测（推荐用Long.lowestOneBit()配合清除）
关键注意事项与边界处理
- 只支持非负整数：若含 0，下标 0 可用；负数需偏移（如加 offset 映射到正区间），但会扩大范围
- 必须预知最大值：否则无法分配数组。可先扫描一次求 max，或用动态扩容（不推荐，破坏 O(1) 访问）
- 内存 vs 范围权衡：若数据稀疏（如 10 万个数，最大值 1 亿），位图空间浪费严重，此时应选计数排序（用 HashMap）或堆排序
- 线程安全：纯数组操作无锁，但多线程写入需同步；单次构建 + 多次读取则天然安全
何时选择位图排序？
- 输入是不重复的正整数，且范围可控（如用户 ID、状态码、小范围索引）
- 要求极致速度，且允许牺牲内存（如嵌入式缓存、日志分析中间步骤）
- 实际场景举例：统计某天 PV 中出现过的 URL 编号（编号 1～50 万）、游戏内道具 ID 排序展示
Java免费学习笔记：立即使用
解锁 Java 大师之旅：从入门到精通的终极指南
