八、外部排序

八、外部排序

前面第七章介绍了内部排序需要把待排序数据全部放入内存中，然后再排序。这就限制了待排序数据的规模。当数据量特别大时，程序的内存空间有可能放不下。所以我们需要把大文件分几次读入内存，对每次读入的数据进行内部排序，生成几个有序的子文件；再将这几个有序文件通过外部排序方法归并到一个有序大文件中。

1. 多路平衡归并

将多个有序子文件归并成一个有序大文件时，每归并一次就要在外存读入一次数据。如果要减少归并次数，就要进行多路归并（同时将几个文件进行归并）。而多路归并要在多个关键字中比较，才能找到最小值。利用 “败者树” 可减少比较次数。

“败者树” 是一棵完全二叉树，因此用顺序结构存储。但它是由两种不同类型的结点组成的：
（1）叶子结点：是外部结点，其类型为数据类型。每个叶子结点中的值为从相应的有序子文件读出的当前数据。叶子结点的个数恰为待归并的文件数 k 。
（2）非叶子结点：是度为 2 的内部结点，其类型为整型，存储叶子结点的序号。根结点在 [1] 。非叶子结点的个数 = k（叶子结点的个数）-1 。

每个非叶子结点中的值为其左右两棵子树中的两个胜者相比时，其中败者的序号，胜者再向上一级去比较。

最终的胜者结点的序号存于败者树的根节点之上的 [0] ，再存于大文件中。胜者原先所在的有序子文件的下一个数据取代胜者在叶子结点中的位置，继续比较，求出新的胜者。和堆排序类似，在继续比较时，它不必和所有叶子的关键字去比较，只须沿着从相应的叶子到根的路径去调整 “败者树” 。这就大大减少了比较次数。

一个新的叶子结点取代胜者加入到这棵 “败者树” 中，要形成新的 “败者树” ，即求出新的最小值，需要进行比较的次数 = 这个结点所在层数 - 1 。

实现：

//败者树类
template<typename D>class LoserTree
{//带模板的败者树类
private:
  int k;  //k 路归并
  int *ls;  //败者树非叶子结点指针
  D *b;  //败者树叶子结点指针
  ifstream *fin;
  ofstream fout;
  void Adjust(int i)
  {//沿着叶子结点 b[i] 到根结点 ls[1] 的路径调整败者树，胜者存 ls[0]
    int t;
    t = (i + k) / 2;
    while(t > 0)
    {
      if GT(b[i].key, b[ls[t]].key)
        swap(i, ls[t]);
      t = t / 2;
    }
    ls[0] = i;
  }
  void CreateLoserTree()
  {//沿着序号最大的叶子到根的 k 条路径将 ls 调整成为败者树
    int i;
    b[k].key = MIN;
    for(i = 1; i < k; i++)
      ls[i] = k;
    for(i = k-1; i >= 0; i--)
      Adjust(i);
  }
public:
  LoserTree(int num)
  {//构造函数
    k = num;
    ls = new int[k];
    b = new D[k + 1];
    fin = new ifstream[k];
    char s[7] = "F0.txt";  //文件名
    for(int i = 0; i < k; i++)
    {
      s[i] = i + '0';  //将数字 i 转换为字符
      fin[i].open(s, ios::in);
    }
    s[i] = k + '0';
    fout.open(s, ios::out);
  }
  ~LoserTree()
  {//析构函数
    delete[] ls;
    delete[] b;
    for(int i = 0; i < k; i++)
      fin[i].close();
    delete[] fin;
    fout.close();
  }
  void K_Merge()
  {//k 路归并
    int j = 0;
    for(int  i = 0; i < k; i++)
      InputFromFile(fin[i], b[i]);
    CreateLoserTree();
    char s[7] = "F0.txt";  //文件名
    s[1] = k + '0';
    cout << "有序大文件" << s << "的数据为" << endl;
    while(b[ls[0]].key != MAX)
    {
      visit(b[ls[0]]);
      if (++j % M == 0)
        cout << endl;
      OutputFile(fout, b[ls[0]]);
      if (!fin[ls[0].eof()])
        InputFromFile(fin[ls[0]], b[ls[0]]);
      else
        b[ls[0]].key = MAX;
      Adjust(ls[0]);
    }
  }
};

2. 置换-选择排序

要提高外部排序的效率，除了选择 “败者树” 归并方法外，还应该尽量使有序子文件较长，从而减少待归并文件的数量。

置换-选择排序采取增多待排序数据个数的方法使生成的有序子文件更长。具体算法是：逐个把已排序的数据送入外存，再从大文件读入一个数据到内存空出的位置，只要这个数据的关键字不小于刚送到外村的关键字，该数据就会排到当前有序子文件中。

置换-选择排序在搜索内存中的最小值时，也是采用败者树。和多路平衡中的败者树不同的是，叶子结点多了一个存储数据段号的 mum 域。如果新读入数据的关键字小于刚送到外存的数据的关键字，则设置新读入数据的段号比刚送到外存的数据的段号大 1 ，标志新读入的数据不排在当前的有序子文件中。

实现：

//置换-选择排序类
template<typename D>class Replace_Select
{//带模板的置换-选择排序类
private:
  struct WA  //内存工作区的结构体
  {
    D rec;  //数据
    int rnum;  //所属归并段的段号
  };
  int k;  //k 路归并
  WA *wa;  //内存工作区指针
  int *ls;  //败者树非叶子结点指针
  void Select_MiniMax(int q)
  {//从 wa[q] 起到败者树的根比较选择当前段的最小数据给 ls[0]
    for(int t = (k + q) /2; t > 0; t = t / 2)
      if (LT(wa[ls[t]].rnum, wa[q].rec.key) || EQ(wa[ls[t].rnum, wa[q].rnum]) 
          && LT(wa[ls[t]].rec.key, wa[q].rec.key))
        swap(q, ls[t]);
    ls[0] = q;
  }
  void Construct_Loser(ifstream &f)
  {//输入k个数到wa[]，创建败者树ls[]，选出关键字最小的数据，ls[0]指示其在wa中的位置
    int i;
    for(i = 0; i < k; i++)
      wa[i].rnum = ls[i] = 0;
    for(i = k-1; i >= 0; i--)
    {
      InputFromFile(f, wa[i].rec);
      wa[i].rnum = 1;
      Select_MiniMax(i);
    }
  }
  void get_run(int rec, int &rmax, ifstream &fi, ofstream &fo)
  {//求得一个归并段，fi 为输入文件指针， fo 为输出文件指针，rc 为当前段
    int q;
    KeyType minimax;
    while(wa[ls[0]].rnum == rc)
    {
      q = ls[0];
      minimax = wa[q].rec.key;
      OutputFile(fo, wa[q].rec);
      visit(wa[q].rec);
      InputFromFile(fi, wa[q].rec);
      if (fi.eof())
        wa[q].rnum = rmax + 1;
      else
      {
        if LT(wa[q].rec.key, minimax)
        {
          rmax = rc + 1;
          wa[q].rnum = rmax;
        }
        else
          wa[q].rnum = rc;
      }
      Select_MiniMax(q);
    }
  }
public:
  Replace_Select(int num)
  {//构造函数，num 为内存工作区可容纳的数据个数
    k = num;
    ls = new int[k];
    wa = new WA[k];
  }
  ~Replace_Select()
  {//析构函数
    delete[] ls;
    delete[] wa;
  }
  void Replace_Selection(char* FileName)
  {//用置换-选择排序将无序大文件生成若干尽量长的有序子文件
    ifstream fin(FileName);
    int rc, rmax;
    char s[7] = "F0-txt";  //有序子文件名
    Construct_Loser(fin);
    rc = rmax = 1;
    do
    {
      s[1] = rc - 1 + '0';
      ofstream fout(s);
      cout << s << "的内容是";
      get_run(rc, rmax, fin, fout);
      cout << endl;
      fout.close();
      rc = wa[ls[0]].rnum;
    }while(rc <= rmax);
    cout << "共产生" << rc-1 << "个初始归并段文件" << endl;
  }
};