位排序

该文主要来自于编程珠玑第一章上的题目。

输入：一个最多包含n个正整数的文件，每个数都小于n，其中n=10^7。如果在输入文件中有任何证书重复出现就是致命错误。没有其它数据与该整数关联。

输出：按升序排列的输入整数的列表。

约束：最多有（大约）1MB的内存空间可用，有充足的磁盘空间可用。运行时间最多为几分钟，运行时间为10秒就不需要进一步优化了。

解决方案，定义一个位向量，如bit_vector[10000000]，初始化为0；遍历文件中的每个正整数i，设置bit_vector[i]为1。最后，遍历bit_vector，输出元素为1的下标。

下面给出代码，位向量的实现程序

#ifndef BIT_VECTOR
#define BIT_VECTOR
/*
 * bit_vector.h
 *
 * 使用二进制位存放向量的数据结构。举个例子，如果我们有个向量{1,2,4,7,15}，
 * 那么，用二进制位可以表示成 10000000 10010110，从右往左看，第n位为1表示
 * n处在向量中（从0开始）。
 *
 * 使用示例：
 * bit_vector bv(64); // 能存放[0, 64)的整数
 * bv.put(0);
 * bv.print();
 * bv.put(63);
 * bv.print();
 * bv.get(0); // 1
 * bv.get(1); // 0
 * bv.get(63); // 1
 */
#include <cstdio>
#define INT_BITS (sizeof(int)*8)

class bit_vector {
  int * bits_;
  int n_;

public:
  // 申请n位的位向量，并初始化为0
  bit_vector(int n=INT_BITS){
    n_ = n / INT_BITS;
    if (n % INT_BITS != 0) {
      n_++;
    }
    bits_ = new int[n_];
    for (int i=0; i<n_; ++i) {
      bits_[i] = 0;
    }
  }

  // 清除申请的内存
  ~bit_vector() {
    delete bits_;
  }

  // 把数m放入位向量中，即位向量的第m位置为1
  void put(int x) {
    int i = x / INT_BITS;
    int j = x % INT_BITS;
    bits_[i] |= 1 << j;
  }

  // 把第x位重置为0
  void clear(int x) {
    int i = x / INT_BITS;
    int j = x % INT_BITS;
    bits_[i] &= ~(1 <<j );
  }

  // 如果数x在位向量中，返回不为0，否则返回0
  int get(int x) {
    int i = x / INT_BITS;
    int j = x % INT_BITS;
    return bits_[i] & 1 << j;
  }

  // 打印出位向量
  void print() {
    for (int i=n_-1; i>=0; --i) {
      printf("%08x ", bits_[i]);
    }
    printf("\n");
  }
};
#endif // BIT_VECOTR

生成测试数据的程序

/*
 * gen_data.cc
 *
 * 生成[0,n)之间的k个不同的随机顺序的随机整数。
 *
 * 主要思想是定义个长度为n的数组a，a[i]=i。第一次从a[0:n-1]中随机取个
 * 元素，并和a[n-1]调换。第二次，从a[0:n-2]中随机取个元素，并和a[n-2]调换。
 * 经过k次这样的调换之后，a[n-k-1,n-1]就是我们需要的随机整数序列。
 *
 * 不计算初始化数组的复杂度，复杂度为O(k)。
 */
#include <cstdio>
#include <cstdlib>
#define N 10000000
#define K 1000000

int main(int argc, char *argv[])
{
  int *a = new int[N];
  for (int i=0; i<N; ++i) {
    a[i] = i;
  }

  int end = N;
  while (N-end <= K) {
    int r = rand() % end; // 取随机数r in [0, end)

    int temp = a[r];
    a[r] = a[end-1];
    a[end-1] = temp;

    end--;
  }

  FILE* out_file = fopen("data.txt", "w");
  for (int i=N-K; i<N; i++) {
    fprintf(out_file, "%08d\n", a[i]);
  }
  fclose(out_file);

  delete a;

  return 0;
}

主程序文件：

#include "bit_vector.h"
#include <cassert>

#define N 10000000

int main(int argc, char *argv[])
{
  FILE* in_file = fopen("data.txt", "r");
  bit_vector bv(N);

  int x;
  while (!feof(in_file)) {
    fscanf(in_file, "%d\n", &x);
    bv.put(x);
  }
  fclose(in_file);

  FILE * out_file = fopen("sorted_data.txt", "w");
  for (int i=0; i<N; ++i) {
    if (bv.get(i) != 0) {
      fprintf(out_file, "%08d\n", i);
    }
  }
  fclose(out_file);

  return 0;
}

组织文件Makefile和run.sh：

all:
g++ -Wall -o main main.cc
g++ -Wall -o gen_data gen_data.cc

make
./gen_data
./main
wc -l data.txt sorted_data.txt