学步园

1、1000w个整数（没有重复）进行排序，可用内存只有1M，怎么排序？

     1000w *4 /（1024*1024）= 38.14 M ;

     所以划分40个通道,每次读取25w个数据（需要不到1M内存）,利用快速排序或者堆排序进行排序，然后写回到文件中;

     对得到的40个排好序的文件两两进行归并排序，直到得到一个排好序的文件即可。

2、1000w个整数（没有重复）进行排序，内存不限，怎么排序？

     用位图排序（C语言代码如下）

1.#include <stdio.h> 
2.#include <stdlib.h>  
3.#define BITSPERWORD 32       //int类型32位
4.#define SHIFT 5  
5.#define MASK 0x1F            //掩码，用来和i求与
6.#define N 10000000  
7.int a[1 + N/BITSPERWORD];    //数组a中每个元素有32位，可以用来存储32个元素
8.
9.void set(int i) {        a[i>>SHIFT] |=  (1<<(i & MASK)); }         //设置某位是为1或者0
10.void clr(int i) {        a[i>>SHIFT] &= ~(1<<(i & MASK)); }        //将该位清0
11.int  test(int i){return a[i>>SHIFT] &   (1<<(i & MASK)); }         //返回某位的值
12.
13.int main()  
14.{       int i = 0, top = 1 + N/BITSPERWORD;
15.        memset(a, 0, sizeof(a)*sizeof(int));
16.        while (scanf("%d", &i) != EOF) set(i);
17.        for (i = 0; i < N; i++)
18.                if (test(i)) printf("%d\n", i);
19.        return 0;  
20.}

3、C++中bitset位操作符介绍

      bitset基本操作如下：

#include <stdio.h>  
#include <stdlib.h>
#include <iostream>
#include <bitset>
using namespace std;

int main()
{	
	bitset<10> b;          //b有10位，每位都为0
	
	cout<<b<<endl;

	for (int i=0;i<10;i++)
	{
		if (i%2==0)
		{
			b.set(i);      //设置b的某一位为1
		}
	}
    cout<<b<<endl;

	b.reset();             //全部置0
	b.set();               //全部置1
	cout<<b<<endl;

	cout<<b.test(5)<<endl;  //第5位是否为1
	cout<<b.any()<<endl;    //b中是否存在置为1的二进制位
	cout<<b.none()<<endl;   //b中是否不存在置为1的二进制位
	cout<<b.count()<<endl;  //b中置为1的二进制位个数

    return 0;	
}

4、利用bitset重写位图排序代码

#include <stdio.h>  
#include <stdlib.h>
#include <iostream>
#include <bitset>
using namespace std;

#define N 100000000   //最多N个数
bitset<N> b;         //b有N个位

int main()
{

	int i;
	while(cin>>i)
	{
		b.set(i);               //将该位设置为1
	}

	for(i=0;i<N;i++)
	{
		if(b.test(i))           //输出位为1对应的数值
			cout<<i<<" ";
	}
	cout<<endl;

	b.reset();                  //将b所有位重置为0
    return 0;	
}