如何对 1 千万个整数进行快速排序

问题原型

一个最多包含 n 个正整数的文件，每个数都小于 n，其中 n = 10^7。此 n 个正整数不存在重复。请将这 n 个正整数按照升序排列。

问题约束

最多有大约 1MB 的内存空间可用，有充足的磁盘存储空间。运行时间最多几分钟，运行时间小于 10 秒。

问题分析

首先我们来看10^7个整数需要占用的空间大小 4*10^7个byte，即约 40MB 的空间，由于内存空间的限制，我们不可能把所有的数据同时读入内存中，但是由于磁盘空间充足我们可以将文件先存档到磁盘中，然后逐次来读写文件中的数据进行处理。

其次考虑用常规的排序方式进行数据排序的话，必然要分批进行排序，显然这将是一个耗时耗资源的事情。我们需要考虑其他方式来进行排序。通常对于处理大数据的常用位图法进行。

再次此处由于n个数是均小于n的非重复整数，故我们可以考虑用n个bit来表示n个整数，则需要的空间可以缩小 8 倍，也就是 10^7个整数需要 10^7 / 8 = 1.2 MB 空间。

问题解决

算法流程：
1、对给定大小的数组所有的比特位置0
2、循环读取输入文件的数据，并将对应数值大小的比特位置1
3、遍历数组各比特位，如果位为1，则输出对应比特位的位置整数。

c语言实现：

  1 #include<stdio.h>
  2 #include<stdlib.h>
  3 
  4 #define CHAR_BIT   8  
  5 #define SHIFT      3
  6 #define MAX_NUM    10000000
  7 #define BIT_SIZE   10000000*8
  8 #define MAX_STR      10 //一个整数的最大字符数
  9 
 10 #define INPUT_FILE   "src_num.txt"
 11 #define OUTPUT_FILE   "dst_num.txt"
 12 
 13 int putIntoBitMap(char *bitmap, int num)
 14 {
 15     if(NULL == bitmap)
 16         return -2;
 17     if(num >= MAX_NUM || num < 0)
 18         return -1;
 19     int byte = num >> SHIFT;
 20     char bit = 1 << (num % CHAR_BIT);
 21     bitmap[byte] |= (char)bit;
 22    return 0;               
 23 }                          
 24                            
 47         fclose(in);
 48         return -1;
 49     }      
 50     int num = 0;
 51     while(fgets(string, NAX_STR, in) != NULL)
 52     {      
 53         num = atoi(string);
 54         putIntoBitMap(bitmap, num);
 55     }      
 56     fclose(in);
 57            
 58     /*遍历位图中的比特位，为1，则输出整数到文件中*/
 59     FILE *out = fopen(OUTPUT_FILE, "w+");
 60     if(NULL == out)
 61     {      
 62         printf("open dst num failed");
 63         free(bitmap);
 64         bitmap = NULL;
 65         return -1;
 66     }      
 67     int i; 
 68     for (i = 0; i < BIT_SIZE; i++)
 69     {      
 70         if (isInBitMap(bitmap , i)) 
 71         {  
 72             fprintf(out, "%d\n", i);
 73             //printf("%d\n",i);        
 74         }                              
 75                                        
 76     }                                  
 77     fclose(out);                       
 78     free(bitmap);                      
 79     bitmap = NULL;                     
 80     return 0;
 81 }