位图排序是内存受限下海量整数排序的高效方案：一、分段位图降低内存峰值；二、mmap映射临时文件实现外存扩展；三、动态位宽压缩（如elias-fano）优化稀疏数据存储。
如果您需要对海量整数数据进行排序，但内存资源受限，则位图排序是一种高效的空间优化方案。以下是实现该算法的具体步骤：
一、使用分段位图降低单次内存占用
将整个数据值域划分为多个连续子区间，每个区间独立构建位图，避免一次性申请过大内存块。每个子位图仅覆盖其对应范围内的整数存在状态，从而将峰值内存使用压缩至可接受水平。
1、确定整数取值范围，例如 [0, 10^8)，将其按每 10^6 个数划分为 100 个段。
2、为每一段分配一个大小为 10^6 / 8 字节的 char 数组，初始化为全 0。
3、遍历原始数据流，根据数值计算所属段号及段内偏移，将对应 bit 置为 1。
4、按段号顺序扫描各段位图，对每个段内已置位的偏移量加回段基址，输出有序结果。
二、采用 mmap 映射临时文件模拟位图内存
当总位图容量仍超出物理内存时，可借助操作系统的内存映射机制，将位图结构映射到磁盘临时文件，由内核按需换入换出页，避免程序主动管理内存与磁盘交换逻辑。
1、创建一个大小等于位图所需字节数的临时文件，使用 ftruncate 设置长度。
2、调用 mmap 将该文件以 PROT_READ | PROT_WRITE 权限映射为可读写内存区域。
3、将整数逐个转换为全局 bit 偏移，通过位运算在映射内存中设置对应 bit。
4、遍历映射内存，对每个非零字节执行 __builtin_popcount 检查，并结合字节内位置还原原始整数。
三、启用动态位宽压缩存储标志位
针对稀疏数据场景，若实际输入整数数量远小于值域跨度，可放弃固定 1-bit 表示法，改用 Elias-Fano 编码等紧凑结构仅存储存在的数值，显著减少无效 bit 占用。
1、预扫描全部数据，统计最小值、最大值及总数 N，估算密度比 ρ = N / (max - min + 1)。
2、若 ρ
3、高位部分以单调递增序列形式存储，使用差分+Unary 编码；低位部分以定长 ⌈log₂(max−min+1)⌉ 存储。
4、排序输出时直接按编码顺序解码，无需展开为完整位图。
四、利用 SIMD 指令加速位图扫描
在输出阶段批量检测位图中连续字节的非零模式，借助 AVX2 的 _mm256_testz_si256 等指令一次判断 32 字节是否全零，跳过空闲区域，提升扫描吞吐率。
1、将位图按 32 字节对齐分块，每块加载进 ymm 寄存器。
2、使用 _mm256_testz_si256 判断该寄存器是否全零；若为真，则跳过整个块。
3、对非零块调用 _mm256_movemask_epi8 提取每个字节最高位构成 32-bit 掩码。
4、对掩码中每个置位的 bit 位置，结合字节索引和位索引计算原始整数并输出。
五、多线程分片写入与归并读取
将输入数据按哈希或范围划分给多个线程，各自维护局部位图；写入完成后，主线程按序合并各局部位图的输出流，实现无锁并发写入与有序读取分离。
1、启动 T 个线程，每个线程绑定一个独立的位图对象（如 std::vector<:atomic>>）。
2、主程序按整数模 T 对输入数据分流，发送至对应线程队列。
3、各线程消费队列，将数值映射到本地位图并原子置位。
4、所有线程完成写入后，主线程按线程序号依次扫描其位图，确保输出严格保持全局升序。
C++免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 C++ 的入门与实战技巧！
