C 版 位图排序法

C 版 位图排序法

问题： 给10^7 个 不重复的整数， 排序

位图实现：

基本思路： 使用一位来表示一个数 例如集合 {1， 3， 5， 8}，  可以用 位图 {10101001} 来表示。即对应位置为1 如下图所示.

关键操作有： 1） 找到数据所对应的字节位置 2）找到数据对应的字节中位位置 3） 判断某位为1， 置某位为1 etc

方法：

1） 找到 对应字节位置: 如果系统是32 位的话 相当于将 数据/32, 使用位操作 数据 >> 5

2)  找到对应字节的位位置: 如果系统是32位的话 相当于将 数据%32, 使用位操作 数据 &0x1F

3）数字 a 的 第i位 是1： 方法 a & (1 << i) ，将数据a的第 i位 置1 a | (1 << i)

具体步骤：

#define MAX 5000000
#define SHIFT 5
#define MASK 0x1F
#define DIGITS 32

int bitmap[1 + MAX/DIGITS];

// 先找到数据n 所在位置bitmap[n >> SHIFT]
// 然后将这个整数的 所对应的数据n的位置 置1； (n & MASK) 是找到对应为位位置； 与运算 置1
void set(int n)
{
    bitmap[n >> SHIFT] = bitmap[n >> SHIFT] | (1 << (n & MASK));
}

// 置0 采用 & 运算
void clear(int n)
{
    bitmap[n >> SHIFT] = bitmap[n >> SHIFT] & (~ 1 << (n & MASK));
}

//采用 & 运算
void test(int n)
{
      return bitmap[n >> SHIFT] & (1 << (n & MASK));
}

int main()

{

 for(int i = 1; i <= MAX; i++)
 {
    clear(i);
  }

  // open data file with unsorted data
  FILE *fp_unsort_file = fopen("data.txt", "r");
  assert(fp_unsort_file);
  FILE* fp_sort_file = fopen("sortByC.txt", "w");
  assert(fp_sort_file);

  int n;
  while(fscanf(fp_unsort_file, "%d ", &n) != EOF)
  {
    set(n%MAX);
  }

  for(int i = 1; i <= MAX; i++)
  {
   if(test(i))
    {
     fprintf(fp_sort_file, "%d ", i);
    }
  }

  if(fp_unsort_file != NULL)
  {
    fclose(fp_unsort_file);
  }
  if(fp_sort_file != NULL)
  {
    fclose(fp_sort_file);
  }

}

另外C++ 实现了bitmap 也可以直接用
 
C++ 标准的STL

1. // 初始化
2. bitset<max_each_scan> bit_map;
3. bit_map.reset();
4. // 置1
5. while(fscanf(fp_unsort_file, "%d ", &n) != EOF)
6. {
7. if(num < max)
8. {
9. bit_map.set(n, 1);
10. }
11. }
12. // 判断
13. for (int i = 0; i < max; i++)
14. {
15. if(bit_map[i] == 1)
16. {
17. fprintf(fp_sort_file, "%d ", i);
18. }
19. }

《C++ 设计新思维》 下载见

C++ Primer Plus 第6版 中文版 清晰有书签PDF+源代码

读C++ Primer 之构造函数陷阱

读C++ Primer 之智能指针

读C++ Primer 之句柄类

将C语言梳理一下，分布在以下10个章节中：

1. Linux-C成长之路（一）：Linux下C编程概要
2. Linux-C成长之路（二）：基本数据类型
3. Linux-C成长之路（三）：基本IO函数操作
4. Linux-C成长之路（四）：运算符
5. Linux-C成长之路（五）：控制流
6. Linux-C成长之路（六）：函数要义
7. Linux-C成长之路（七）：数组与指针
8. Linux-C成长之路（八）：存储类，动态内存
9. Linux-C成长之路（九）：复合数据类型
10. Linux-C成长之路（十）：其他高级议题

本文永久更新链接地址：