外部排序，则是每次进行部分排序，然后将各组部分排序的结果合并，再次排序得到最终的结果．

本文中的程序用最大堆和最大赢者树完成了一个外部排序算法，基本思想如下：

  1. 将Ｎ个元素的大数组拆成每个元素为Ｍ的子数组，得到X=(N/M)个子数组；
  2. 对这Ｘ个子数组，依次使用堆排序进行排序；
  3. 初始化最大赢者树：取出这Ｘ个子数组的最大元素，初始化一颗Ｘ个元素的最大赢者树；
  4. 每次从最大赢者树弹出一个最大值后，再从对应最大堆里面取出一个次大元素，补充进最大赢者树；
  5. 不停循环步骤４，直到所有最大堆里的元素都被弹出．

外存交互方式

为了便于分别管理子数组，这里使用文件存放每一个子数组，一个子数组存放到一个文件里面，记录下来其对应的文件名。使用vector fileNames记录每一个子数组文件名称。

子数组内部排序

这里使用c++ 提供的快速排序算法。从原始的输入文件里面一次读入vector arr，这里将arr大小,即每一个子数组大小，设置为heap_size。当数组存满时，便排序后写入外存文件，再清空数组。

  1. if(arr.size()==heap_size)
  2. {
  3.   sort(arr.begin(),arr.end(),greater<int>());//降序排列
  4.   out.open(fileNames[i++]);
  5.   if (!out)
  6.   {
  7.   cout << "文件不能打开" <return -1;
  8.   }
  9.   for(int s:arr){
  10.   out<" ";
  11.   }
  12.   out<close(); 
  13.   arr.clear();   
  14. }

最大赢者树

c++提供了现成的堆：优先队列，这里为了找到堆中每一个元素所属于哪一个子数组（文件），堆里存放的是元素和其对应的子数组的外存位置（文件名）：pair = make_pair(待排序元素，所在文件名)，采用自定义堆排序：根据待排序元素大小构建一个大顶堆

  1. /**
  2. 自构建比较函数
  3. **/
  4. struct cmp
  5. {
  6.     bool operator()(Pair a, Pair b) { 
  7.         return a < b; //利用pair的重载运算符
  8.     }
  9. };
  11. priority_queue, cmp > Tree; //使用大顶堆构造最大赢者树

初始化大顶堆后删除每一个子数组文件的头一个元素（最大值），表示该元素由外存引入内存。然后依次弹出大顶堆第一个元素（最大值）写入结果文件中。

每次从最大赢者树弹出一个最大值后，再从对应最大堆里面取出一个次大元素，补充进最大赢者树，刷新大顶堆。

这里都需要用到从文件中删除头一个元素的操作：

  1. /**
  2.  * 删除文件头一个元素以及其后面的空格,并返回文件的第一个原素
  3.  * 文件为空返回false*/
  4. bool delFirstElement(string fileName,int * firstElement)
  5. {
  6.     vector<int> arr;
  7.     int data;
  8.     std::ifstream inputs(fileName);
  9.     while(inputs>>data)
  10.     {
  11.         arr.push_back(data);
  12.     }
  13.     inputs.close();
  14.     if(arr.empty())
  15.     {
  16.         return false;
  17.     }
  18.     std::ofstream outs(fileName);
  19.     if(arr.size()>1)
  20.     {
  21.         for(int i = 1;isize();++i)
  22.             outs<" ";
  23.     }
  24.     outs<0];
  25.     outs.close(); 
  26.     return true;
  27. }

测试案例生成

按道理，测试案例的输入文件应该是一个超过内存的足够多的数字的文件：比如存放了100亿个数字的文件。

这里为了测试方便，就从内存随机生成了一组数字，自己写到输入文件中

  1. bool generateData(string inputsFileName,int total_nums, int heap_size)
  2. {
  3.       /*
  4.      * 生成原始数据, 一行 heap_size 个元素,依此打印出来
  5.      */
  6.     ofstream out;
  7.     out.open(inputsFileName);
  8.     if (!out)
  9.     {
  10.         cout << "文件不能打开" <close();
  11.         return false;
  12.     }
  13.     printf("Input Array: \n");
  14.     for(int i = 1; i <= total_nums; i++) 
  15.     {
  16.         int number = rand()%1000;;
  17.         if(i%heap_size == 1)
  18.             printf("%3d - %3d: ", i, i + heap_size-1);
  20.         printf("%3d ", number);
  21.         out<" ";
  22.         if(i%heap_size == 0)
  23.         {
  24.             printf("\n");
  25.             out<printf("\n\n");
  26.     out<close();
  27.     return true;
  28. }

完整代码

  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <string.h>
  4. #include <fstream>
  5. #include <iostream>
  6. #include <queue>
  7. #include <random>
  8. #include <time.h>
  9. #include <algorithm>
  10. #include <utility>
  11. #include <math.h> 
  12. using namespace std;
  14. typedef pair<int,string> Pair;
  15. /**
  16. 自构建比较函数
  17. **/
  18. struct cmp
  19. {
  20.     bool operator()(Pair a, Pair b) { 
  21.         return a < b; //利用pair的重载运算符
  22.     }
  23. };
  25. bool generateData(string inputsFileName,int total_nums, int heap_size)
  26. {
  27.       /*
  28.      * 生成原始数据, 一行 heap_size 个元素,依此打印出来
  29.      */
  30.     ofstream out;
  31.     out.open(inputsFileName);
  32.     if (!out)
  33.     {
  34.         cout << "文件不能打开" <close();
  35.         return false;
  36.     }
  37.     printf("Input Array: \n");
  38.     for(int i = 1; i <= total_nums; i++) 
  39.     {
  40.         int number = rand()%1000;;
  41.         if(i%heap_size == 1)
  42.             printf("%3d - %3d: ", i, i + heap_size-1);
  44.         printf("%3d ", number);
  45.         out<" ";
  46.         if(i%heap_size == 0)
  47.         {
  48.             printf("\n");
  49.             out<printf("\n\n");
  50.     out<close();
  51.     return true;
  52. }
  53. /**
  54.  * 删除文件头一个元素以及其后面的空格,并返回文件的第一个原素
  55.  * 文件为空返回false*/
  56. bool delFirstElement(string fileName,int * firstElement)
  57. {
  58.     vector<int> arr;
  59.     int data;
  60.     std::ifstream inputs(fileName);
  61.     while(inputs>>data)
  62.     {
  63.         arr.push_back(data);
  64.     }
  65.     inputs.close();
  66.     if(arr.empty())
  67.     {
  68.         return false;
  69.     }
  70.     std::ofstream outs(fileName);
  71.     if(arr.size()>1)
  72.     {
  73.         for(int i = 1;isize();++i)
  74.             outs<" ";
  75.     }
  76.     outs<0];
  77.     outs.close(); 
  78.     return true;
  79. }
  81. int main(int argc, char **argv)
  82. {
  83.     int total_nums, heap_size;
  84.     int data;
  85.     int Ｘ = 0;
  86.     int * firstElement = new int(0);
  87.     vector<int> arr;
  88.     ifstream inputs;
  89.     ofstream out;
  90.     string inputsFileName = "./data.txt";
  91.     string outputFileName = "./sortedData.txt";
  92.     vector fileNames;
  93.     srand( (unsigned)time( NULL ) );//srand()函数产生一个以当前时间开始的随机种子
  95.     if(argc != 3) 
  96.     {
  97.         printf("Usage like : ./outerSort 10 100\n");
  98.         return -1;
  99.     }
  100.     heap_size  = atoi(argv[1]);
  101.     total_nums = atoi(argv[2]);
  103.     if(heap_size < 2) {
  104.         printf("Usage: The 3th parameter should be larger than 1. Now it's %d.\n", heap_size);
  105.         return -1;
  106.     }
  108.     if(total_nums <= heap_size) {
  109.         printf("Usage: The 2nd parameter should be larger than the 3th parameter.\n");
  110.         return -1;
  111.     }
  112.     Ｘ = ceil((double)total_nums/heap_size);//子数组个数
  113.     for(int i=0;i< Ｘ;++i)
  114.     {
  115.         fileNames.push_back("./out_"+to_string (i)+".txt");
  116.     }
  117.     if(!generateData(inputsFileName,total_nums, heap_size)){
  118.         return -1;
  119.     }
  121.     inputs.open(inputsFileName);
  122.     if (!inputs)
  123.     {
  124.         cout << "文件不能打开" <return -1;
  125.     }
  126.     int i = 0;
  127.     //对这Ｘ个子数组，依次使用堆排序进行排序；
  128.     while(inputs>>data)
  129.     {
  130.         arr.push_back(data);
  131.         if(arr.size()==heap_size)
  132.         {
  133.             sort(arr.begin(),arr.end(),greater<int>());//降序排列
  134.             out.open(fileNames[i++]);
  135.             if (!out)
  136.             {
  137.                 cout << "文件不能打开" <return -1;
  138.             }
  139.             for(int s:arr){
  140.                 out<" ";
  141.             }
  142.             out<close(); 
  143.             arr.clear();   
  144.         }
  145.     }
  146.     inputs.close();
  148.     //初始化最大赢者树：取出这Ｘ个子数组的最大元素，初始化一颗Ｘ个元素的最大赢者树；
  149.     priority_queue, cmp > Tree; //使用大顶堆构造最大赢者树
  150.     for(string name: fileNames)
  151.     {
  152.         int max;
  153.         // cout<
  154.         inputs.open(name);
  155.         if (!inputs)
  156.         {
  157.             cout << "文件不能打开" <return -1;
  158.         }
  159.         inputs>>max; //第一个就是最大值
  160.         Tree.push(make_pair(max,name));
  161.         inputs.close();
  162.         delFirstElement(name,firstElement);
  163.     }
  164.     //每次从最大赢者树弹出一个最大值后，再从对应最大堆里面取出一个次大元素，补充进最大赢者树；
  165.     out.open(outputFileName);
  166.     if (!out)
  167.     {
  168.         cout << "文件不能打开" <return -1;
  169.     }
  170.      while (!Tree.empty()) {
  171.         cout << Tree.top().first << " ";
  172.         out<< Tree.top().first << " " ;
  173.         string fileName = Tree.top().second;
  174.         Tree.pop();
  175.         if(delFirstElement(fileName,firstElement))//如果不空，取出第一个元素放入最大赢者树
  176.         {
  177.             int secondmax = *firstElement;
  178.             Tree.push(make_pair(secondmax,fileName));
  179.         }
  181.     }
  182.     out.close();
  183.     return 0;
  185. }

程序输出：./Sort 5 20，表示总共20个元素，拆成４个子数组，每个数组元素为5个．

C++ % ./outerSort 5 20
Input Array: 
  1 -   5: 763 375 478 948 822 
  6 -  10: 205 203 333 777  46 
 11 -  15: 175 883 926 696 413 
 16 -  20: 910 680 711 477 327 


948 926 910 883 822 777 763 711 696 680 478 477 413 375 333 327 205 203 175 46 %