问题原型
一个最多包含 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 }
