一，题目：
如何在1MB的空间里面对一千万个整数进行排序？并且每个数都小于1千万。实际上这个需要1.25MB的内存空间（这里所说的空间是考虑用位图表示法时，每一位代表一个数，则1千万/(1024*1024*8) 约为1.25MB ）。
1MB总共有838，8608个可用位。所以估计也可以在1MB左右的空间里面进行排序了。
二，分析：
1）基于磁盘的归并排序（耗时间）
2）每个号码采用32位整数存储的话，1MB大约可以存储250 000 个号码，需要读取文件40趟才能把全部整数排序。（耗时间）
3）位图法，采用一个1千万位的字符串表示每个数，比如{0,2,3}表示为 1 0 1 1 0 0 0 0 。（说明：左边第一位表示 0 第二位表示1 第三位表示 2 。如果有则表示为1，否则为0）遍历每一个整数，有则标记为1，否则标记为0。然后按顺序输出每个整数。这种方法实际需要1.25MB内存，如果可以方便弄到内存的话可以采用此种方法。
4）假如严格限制为1MB，可以采用的策略：两次遍历或者除去第一位为0或1的整数。
生成文件代码：
#!/usr/bin/python
import random
def randDif(k,n):
if k>n:
return []
a = list(range(1,n+1))
random.shuffle(a)
return a[:k]
if __name__=='__main__':
list = randDif(1000000, 10000000)
writedata = open("d:\input.db", "wb")
for i in list:
writedata.write(i)
writedata.close()
//*在min和max之间生成count个不重复的随机数
unsigned int *outoforder(unsigned int min, unsigned int max, unsigned int count)
{
unsigned int i;
static unsigned int *arr, *res;
unsigned int irand, tmp;
unsigned int m = max - min + 1;
arr = (unsigned int *)malloc(m * sizeof(unsigned int));
if(arr == NULL)
return NULL;
res = arr;
for(i = min; i < max; i++)
*arr++ = i;
arr = res;
srand(time(NULL));
for(i = 0; i < count; i++)
{
irand = rand()*MAGIC_RAND%m;
tmp = *arr;
*arr = *(res+irand);
*(res+irand) = tmp;
arr++;
}
return res;
}
位图实现内存略超1M:
因为1000w整数空间用位图存放需要大约3个2的23次方bit，1.5M空间，所以不能一次遍历完。就分三次遍历。100w个1到1000w的随机数，排序在win7.2G内存下大概用了95ms.
#include "stdio.h"
#include "stdlib.h"
#include <string.h>
#include <time.h>
/*数组已假定初始化为0，未考虑数组越界*/
static inline void setbit_t(unsigned int arr[], unsigned int dig)
{
*(arr+(dig>>5)) |= (0x1 << dig%32);
}
unsigned int sort_data(FILE *fin, FILE *fout)
{
unsigned int arr[0x20000] = {0};
unsigned int data[0x20000] = {0};
unsigned int m;
unsigned int n;
//unsigned int count = 0; //保存读取的数字个数
unsigned int i, j;
for(j = 0; j < 3; j++)
{
n = 0;
memset(data, 0, 0x20000*4);
memset(arr, 0, 0x20000*4);
while(1)
{
n = fread(data, 4, 0x20000, fin);
if( n < 0)
return -1;
m = n;
while(n--)
{
if((*(data+n) > (0x1<<22)*j) && (*(data+n) < (0x1<<22)*(j+1)))
{
setbit_t(arr, *(data+n)-(0x1<<22)*j);
/*count++;*/
}
}
if( m != 0x20000)
break;
}
n = 0;
memset(data, 0, 0x20000*sizeof(unsigned int));
for(m = 0; m < 0x20000; m++)
{
if(*(arr+m) != 0)
{
for(i = 0; i < 32; i++)
{
if((*(arr+m)>>i) & 0x1)
{
*(data + n++) = m*32 + i + (0x1<<22)*j;
if( n == 0x20000)
{
fwrite(data, 4, n, fout);
n = 0;
memset(data, 0, 0x20000*sizeof(unsigned int));
}
}
}
}
}
fwrite(data, 4, n, fout);
fseek(fin, 0, SEEK_SET);
}
return 0;
}
int main()
{
FILE *fin, *fout;
fin = fopen("d:\input.db", "rb");
fout = fopen("d:\output.db", "wb");
if((fin == NULL) || (fout == NULL))
{
printf("open file error
");
return 0;
}
sort_data(fin, fout);
fclose(fin);
fclose(fout);
return 0;
}
clock_t s_time= clock();
sort_data(fin, fout);
clock_t e_time= clock();
clock_t reltime = e_time - s_time;
printf("times: %ld", reltime);