位图排序是一种非比较型排序算法，核心思想是用一个二进制位来标记某个整数是否存在，通过位运算实现数据的快速排序、去重和查找，特别适合处理范围明确、数据量大的整数集合场景，相比传统排序算法能大幅降低空间占用。
位图排序基础原理
位图排序的适用前提是明确待排序数据的范围，比如要排序的整数都在0到N之间。我们可以申请一个长度为N+1的位数组，数组的第i位为1就表示整数i存在，为0则表示不存在。排序时只需要遍历一遍数据设置对应位，再按顺序遍历位数组输出为1的位对应的整数即可完成排序。
假设要处理的数据范围是0到9999999，使用传统数组存储每个整数的存在状态需要至少1000万个字节，而使用位图只需要1000万个位，也就是约1.25MB空间，空间优势非常明显。
C++位图基础实现
首先我们需要实现一个基础的位图结构，核心功能包括设置某一位为1、检查某一位是否为1、重置某一位为0。下面是基础位图的实现代码：
#include <vector>
#include <cstdint>
class BitMap {
private:
std::vector<uint8_t> bits; // 用uint8_t数组存储位数据，每个元素存8位
int max_num; // 支持的最大数值
public:
// 构造函数，传入支持的最大数值
BitMap(int max) : max_num(max) {
// 计算需要多少个uint8_t元素，(max + 1 + 7) / 8 向上取整
int size = (max + 1 + 7) / 8;
bits.resize(size, 0);
}
// 设置第num位为1
void set(int num) {
if (num < 0 || num > max_num) return;
int byte_idx = num / 8; // 找到对应的字节索引
int bit_idx = num % 8; // 找到字节内的位索引
bits[byte_idx] |= (1 << bit_idx); // 对应位设为1
}
// 检查第num位是否为1
bool check(int num) {
if (num < 0 || num > max_num) return false;
int byte_idx = num / 8;
int bit_idx = num % 8;
return (bits[byte_idx] & (1 << bit_idx)) != 0;
}
// 重置第num位为0
void reset(int num) {
if (num < 0 || num > max_num) return;
int byte_idx = num / 8;
int bit_idx = num % 8;
bits[byte_idx] &= ~(1 << bit_idx); // 对应位设为0
}
// 获取支持的最大数值
int get_max_num() const {
return max_num;
}
};
空间优化设计
上面的基础实现已经比普通数组节省了大量空间，但还可以进一步优化：如果待处理的数据范围不是从0开始，或者数据分布非常稀疏，我们可以采用偏移量的方式进一步压缩空间。比如待处理数据范围是1000000到2000000，我们可以只申请1000001个位的空间，用输入值减去偏移量1000000作为位索引，进一步减少空间占用。
优化后的位图实现代码如下：
class OptimizedBitMap {
private:
std::vector<uint8_t> bits;
int offset; // 数值偏移量，实际存储的是 num - offset 对应的位
int range; // 数值范围大小，即 max_num - min_num + 1
public:
// 构造函数，传入最小值和最大值
OptimizedBitMap(int min_val, int max_val) {
offset = min_val;
range = max_val - min_val + 1;
int size = (range + 7) / 8;
bits.resize(size, 0);
}
// 设置数值num对应的位
void set(int num) {
int idx = num - offset;
if (idx < 0 || idx >= range) return;
int byte_idx = idx / 8;
int bit_idx = idx % 8;
bits[byte_idx] |= (1 << bit_idx);
}
// 检查数值num是否存在
bool check(int num) {
int idx = num - offset;
if (idx < 0 || idx >= range) return false;
int byte_idx = idx / 8;
int bit_idx = idx % 8;
return (bits[byte_idx] & (1 << bit_idx)) != 0;
}
// 获取排序后的结果
std::vector<int> get_sorted_result() {
std::vector<int> res;
for (int i = 0; i < range; ++i) {
int byte_idx = i / 8;
int bit_idx = i % 8;
if ((bits[byte_idx] & (1 << bit_idx)) != 0) {
res.push_back(i + offset);
}
}
return res;
}
};
完整排序与查找逻辑实现
结合上面的优化位图，我们可以实现完整的海量数据排序和查找功能，下面是完整的测试代码：
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
// 上面的OptimizedBitMap类定义放在这里
int main() {
// 模拟海量数据，范围在1000000到1001000之间，共1001个可能的数值
int min_val = 1000000;
int max_val = 1001000;
OptimizedBitMap bitmap(min_val, max_val);
// 随机生成1000个测试数据，允许重复
std::srand(std::time(nullptr));
std::vector<int> test_data;
for (int i = 0; i < 1000; ++i) {
int num = min_val + std::rand() % (max_val - min_val + 1);
test_data.push_back(num);
bitmap.set(num); // 将数据加入位图
}
// 获取排序后的结果
std::vector<int> sorted = bitmap.get_sorted_result();
std::cout << "排序后数据数量：" << sorted.size() << std::endl;
// 输出前10个排序结果
std::cout << "前10个排序结果：";
for (int i = 0; i < 10 && i < sorted.size(); ++i) {
std::cout << sorted[i] << " ";
}
std::cout << std::endl;
// 测试查找功能
int target = 1000500;
if (bitmap.check(target)) {
std::cout << target << " 存在于数据中" << std::endl;
} else {
std::cout << target << " 不存在于数据中" << std::endl;
}
return 0;
}
算法适用场景与注意事项
位图排序的适用场景非常明确：待排序数据必须是整数，且数值范围已知、不是特别大（或者可以通过偏移量压缩范围）。它的优势是时间复杂度可以达到O(N)，空间复杂度远低于传统排序算法，同时天然支持去重和快速查找。
需要注意的问题：如果数据范围非常大，比如要处理0到10亿的整数，即使使用位图也需要约125MB空间，这时候可以考虑分片处理，把数据分成多个范围分别排序后再合并。另外位图排序无法处理负数、浮点数等非整数类型的数据，这类场景需要选择其他排序算法。
总结
通过C++实现位图排序算法，我们可以高效处理海量整数数据的排序、去重和查找需求，通过偏移量优化可以进一步压缩空间占用。实际开发中可以根据数据的具体范围选择合适的位图实现方式，在时间和空间上取得更好的平衡。上面的源码可以直接编译运行，开发者可以根据自己的需求调整数值范围和测试数据，快速验证位图排序的效果。