第一章只介绍了一个问题，我将问题重新描述一下

• input：一个最多含有n个正整数的文件，每个数都小于n，n = 10^7，输入文件中没有任何整数重复
• output：升序排列的整数列表

程序设计：
思路1：磁盘归并排序
思路2：多趟排序 （这种思路相当于每次先寻找在[start - end]中的数，然后再排序， 略）
思路3：位图排序

磁盘归并排序：
本质也就是多路归并算法，先将大文件分成多个小文件，每个小文件可放入内存中排序，这里的排序算法，我认为可以任意的排序算法，归并排序效率高，但是需要分配额外的内存空间， 这里我先采用快速排序算法。最后将多个小文件依次按照放入最小堆中，每轮弹出一个数，存在一个临时文件里。

为了简化操作，我只是把整个算法实现一遍，当然没有用大数据量去做。
快速排序算法(这是最原始的一种)：

void qsort1(vector<int> &nums, int l, int u) {
    if (l < u) {
        int m = l;
        for (int i = l + 1; i <= u; i++) {
            int num = nums[i];
            if (num < nums[l]) {
                swap(nums[++m], nums[i]);

            }
        }
        swap(nums[m], nums[l]);
        qsort1(nums, l, m - 1);
        qsort1(nums, m + 1, u);
    }
}

然后我在1.txt，2.txt，3.txt随意放了一些数字，将各个小文件排序后重新写入文件中，代码如下：

int getInt(vector<int> &res_array, string s) {
    istringstream iss(s);
    int e, res;
    while(iss >> e)
    {
        res_array.push_back(e);
        res++;
    }
    return res;
}
void from_file(vector<int> &r, fstream& infile) {
    string s;
    while(getline(infile, s))
    {
        getInt(r, s);
    }
}

void write_file(vector<int> &r, fstream& infile) {
    for (auto i: r) {
        infile << i << " ";
    }
}

最小堆可以用stl中的优先队列，优先队列和最大堆（最小堆的区别）具体实现，等我有空再写。
为了简化操作，我直接在内存中采用多路归并排序。
基于文件的多路归并操作先从各个文件中取出一个数，放入优先队列中，然后pop出一个数，然后从这个数对应的文件中再取一个数放入优先队列，如此循环。

最终的测试代码如下：

#include <iostream>
#include <sstream>
#include <fstream>
#include <vector>
#include <queue>
#include <functional>
#include <unordered_map>
using namespace std;
class element {
public:
    element() {}
    element(int i, int x): index(i), n(x) {};
    int get_index() const{
        return index;
    }
    int get_n() const {
        return n;
    }
    bool operator < (const element&) const;
private:
    int index;
    int n;
};
bool element::operator < (const element& e) const{
    return n >= e.n;
}
void quick_sort(vector<int> &v, int l, int u) {
    if (l >= u) {
        return;
    }
    int m = l;
    for (int i = l + 1; i <= u; i++) {
        if (v[i] < v[l]) {
            swap(v[++m], v[i]);
        }
    }
    swap(v[l], v[m]);
    quick_sort(v, l, m - 1);
    quick_sort(v, m + 1, u);
}
int getInt(vector<int> &res_array, string s) {
    istringstream iss(s);
    int e, res;
    while(iss >> e)
    {
        res_array.push_back(e);
        res++;
    }
    return res;
}
void from_file(vector<int> &r, fstream& infile) {
    string s;
    while(getline(infile, s))
    {
        getInt(r, s);
    }
}

void write_file(vector<int> &r, fstream& infile) {
    for (auto i: r) {
        infile << i << " ";
    }
}

int main(int argc, char *argv[]) {
    vector<vector<int>> v(3, vector<int>());
    fstream f1;
    fstream f2;
    fstream f3;
    f1.open("1.txt", fstream::out | fstream::in);
    f2.open("2.txt", fstream::out | fstream::in);
    f3.open("3.txt", fstream::out | fstream::in);
    from_file(v[0], f1);
    from_file(v[1], f2);
    from_file(v[2], f3);
    f1.close();
    f1.clear();
    f2.close();
    f2.clear();
    f3.close();
    f3.clear();
    for (int i = 0; i < v.size(); i++) {
        quick_sort(v[i], 0, v[i].size() - 1);
    }
    unordered_map<int, vector<element>> m;
    for (int i = 0; i < 3; i++)
    {
        vector<element> e;
        for (auto j: v[i]) {
            e.push_back(element(i, j));
        }
        m[i] = e;
    }
    for (auto i: m[2]) {
        cout << i.get_n() <<endl;
    }
    priority_queue<element> q;
    int p[3] = {0, 0, 0};
    for (int i = 0; i <3 ;i++) {
        q.push(m[i][0]);
    }
    vector<int> res;
    while (!q.empty()) {
        cout << "get_n" << q.top().get_n() << endl;
        cout << "get_index " << q.top().get_index() << endl;
        res.push_back(q.top().get_n());
        p[q.top().get_index()]++;
        int index = q.top().get_index();
        if (p[index] >= v[index].size()) {
            ;
        }else {
            q.push(m[index][p[index]]);
        }
        q.pop();
    }
    for (auto i: res) {
        cout << i << endl;
    }
    return 0;
}

---

位图法的实现

首先位图法是用每个bit的位置来表征数的大小的，力求将所有的数放入内存中，然后按序搜索输出即可。
位图法存在以下要求：
正整数，不重复，全部放入内存中。
如果能满足，自然是极快的，因为磁盘i/o开销的时间是内存开销时间的几十倍。
需要实现的功能：
整数到内存空间的映射。
主要api：

unsigned int bit[N]
#define SHIFT 5
#define MAXLINE 32
#define MASK 0x1F

void setbit(int *bm, int i) {
    bm[i >> SHIFT] |= ( 1 << (I & MASK));
}

bool getbit(int *bm, int i) {
    return bm[i >> SHIFT] & (1 << (I & MASK));
}

i & MASK 相当于i %32 ,求位位置 ； i >> SHIFT 相当于 i / 32算字节位置。