第一章只介绍了一个问题，我将问题重新描述一下
- 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算字节位置。
