位图排序适用于非负整数且值域可控的数据，如0到10⁷−1范围内；要求数据不重复、大致范围已知且具有聚集性，最大值过大（如接近INT_MAX）会导致内存激增。
位图排序适合什么数据范围
位图排序只适用于整数，且值域必须可控——比如 0 到 10^7-1 之间的非负整数。超出这个范围，位图占用内存会爆炸：1 亿个不同整数需要约 12.5 MB 内存（10^8 / 8 字节），但若最大值是 INT_MAX（约 21 亿），位图就要 268 MB，还没算去重和排序逻辑开销。
实际使用前务必确认：
– 所有输入都是非负整数（或可统一偏移为非负）；
– 最大值 max_val 满足 max_val （即约 2.68 亿）较安全；<br>– 内存受限但值域窄的嵌入式/日志分析场景比通用排序更合适。
std::vector 不是位图，别直接用
std::vector<bool></bool> 是 C++ 标准库的特化实现，行为上不完全等价于原始位数组：它不支持取地址、迭代器解引用返回 proxy 对象、多线程写入可能出竞态。做排序中间结构时，容易在 set() 或 test() 时触发未定义行为。
推荐方案：
– 用 std::vector<uint8_t></uint8_t> + 手动位运算，清晰可控；
– 或用 std::bitset<n></n>（仅当 N 编译期已知）；
– 更灵活的选型是 std::vector<:byte></:byte>（C++17 起），配合 std::to_integer 和位掩码操作。
立即学习“C++免费学习笔记（深入）”；
示例关键片段：
size_t idx = num / 8;<br>uint8_t mask = 1U << (num % 8);<br>bits[idx] |= mask;
如何处理重复整数和负数
位图天然去重——同一位置只能标记一次。如果业务要求保留重复（如排序后输出每个数出现次数），就不能只用单一位，得升级为「计数位图」：每个数对应一个 uint8_t 或 uint16_t 计数器，空间涨 8 倍起。此时要权衡：是改用哈希表统计 + 桶排序，还是接受去重结果？
负数需偏移转换：
– 找出最小值 min_val；
– 所有数减去 min_val，转为非负；
– 排序后每个结果再加回 min_val；
– 注意偏移后新值域是否仍可控（比如原数据是 [-10^6, 10^6]，偏移后值域是 [0, 2×10^6]，没问题；但若原数据是 [-INT_MAX, INT_MAX]，偏移后直接翻倍溢出，不可行）。
为什么不用 std::sort + 空间换时间不香吗
对千万级随机整数，std::sort 平均 O(n log n)，实测通常 100–300 ms；位图排序理论 O(n + m)（m 是值域大小），但常数大：遍历输入设位、遍历位图收集结果、缓存不友好访问模式。当 m ≈ n × 10 时，位图可能比 std::sort 还慢。
真正快的条件：
– m （比如 1000 万个数，但只分布在 0–50 万之间）；<br>– 输入已高度重复或来自固定采样集（如传感器 ID、HTTP 状态码）；<br>– CPU 缓存能装下整个位图（L3 缓存通常 8–32 MB，对应约 64M–256M bit）。
别为了“位图”二字硬套——先跑个 std::sort baseline，再量 max - min，差两个数量级才值得切。
位图排序最易被忽略的点是值域探测本身开销：扫一遍找 min/max 需要额外 O(n) 时间和一次完整遍历，如果输入是流式或只允许单次读取，这个代价就藏不住了。
