《编程珠玑》第一章

一、题目：

　　如何在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内存，如果可以方便弄到内存的话可以采用此种方法。

二、代码实现

/*C++中的bitset实现位图*/

#include <iostream>
#include<bitset>
using namespace std;

#define MAXNUMBER 10000000

//利用bitset完成在一定范围内的正整数排序，并标准输出
int IntRangeSort(int pdata[],int n)
{
    //static bitset<MAXNUMBER> intset;
    //或者new一个
    bitset<MAXNUMBER> * intset = new bitset<MAXNUMBER>;
    //用位图记录数据
    for(int i = 0;i < n;i++)
        (*intset)[pdata[i]]=1;
        //intset[pdata[i]]= 1;
    //输出有序数据
    for(int i = 0;i < MAXNUMBER;i++)
        //if(intset[i] == 1)
        if((*intset)[i] == 1)
            cout<<i<<" ";
    cout<<endl;
    return 0;
}

void main()
{
     int pdata[10];
     for(int i = 0;i < 10;i++)
     {
         pdata[i] = rand()%10000000;
         cout<<pdata[i]<<" ";
     }
     cout<<endl;
     IntRangeSort(pdata,10);
    system("pause");
}

View Code

注：利用bitset时设置大于1M的栈大小时，vs会报错误（vs默认分配的栈大小约为1M），解决办法是声明为static（相当于将这些数据放于全局数据区）或者 new一个bitset（相当于在栈上分配内存）。

/*用数组实现位图*/ #include <stdio.h> #include<stdlib.h> #define MAXNUMBER 10000000 #define MASK 0x1F #define SHIFT 5 int sets[1+MAXNUMBER/32]; void set(int i){sets[i>>SHIFT] |= (1<<(i & MASK));} void clr(int i){sets[i>>SHIFT] &= ~(1<<(i & MASK)); } int test(int i){return sets[i>>SHIFT] & (1<<(i & MASK));} void main() { int i = 0; while(scanf("%d",&i)) set(i); for(i = 0;i < MAXNUMBER;i++) if(test(i)) printf("%d ",i); system("pause"); }

#include <stdio.h> #include<stdlib.h> #define MAXNUMBER 10000000 int cmp(const void *a,const void *b) { return (*(int*)a) - (*(int*)b); } void main() { static int data[MAXNUMBER]; int n,i; while(scanf("%d",&n) != EOF) { for(i = 0;i < n;i++) scanf("%d",&data[i]); qsort(data,n,sizeof(int),cmp); for(i = 0;i < n;i++) printf("%d ",data[i]); printf(" "); } system("pause"); }

#include <stdio.h> #include<stdlib.h> #define MAXNUMBER 10000000 #define BIN 8 #define MASK 0x07 #define SHIFT 3 #define TEST 0x0F #define POS ((i & MASK)<<2) int sets[1+MAXNUMBER/BIN]; void set(int i){sets[i>>SHIFT] += 1<<POS;} void clr(int i){sets[i>>SHIFT] &= ~(TEST<<POS); } int test(int i){return (sets[i>>SHIFT] & TEST << POS) >> POS;} void main() { int i = 0,j = 0; while(scanf("%d",&i) != EOF) set(i); for(i = 0;i < MAXNUMBER;i++) for(j=test(i);j>0;j--) { printf("%d ",i); printf(" "); } system("pause"); }

相关推荐