bitsort.cpp

不错的排序算法。快速而且占用内存少

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

void RandArray(long Array[],long size,long randnum)  //size Array's size  randnum(range for Array[])
{
	long index = 0;
	long temp = randnum;
	long *TempArray = new long[randnum];
	for(long i = 0;i<randnum;i++)
	{
		TempArray[i] = i;
	}
	srand((double)time(0));
	for(i = 0;i<size;i++)
	{
		index = (long)((double)(randnum)*(double)rand()/(double)(RAND_MAX));
		Array[i] = TempArray[index];
		TempArray[index] = TempArray[randnum-1];
		randnum--;
	}
	randnum = temp;
	delete []TempArray;
}

void BitSort(long Array[],long size,long &temp,long randnum)  //size Array[size] temp after sort Array[temp]
{										// randnum range for Array;
	
	long NUM = 0;
	NUM = randnum/32;
	if((randnum%32) != 0)
		NUM++;

	bitset<32> *bitvec = new bitset<32>[NUM];
	for(long i = 0;i<NUM;i++)
	{
		bitvec[i].reset(0);
	}

	for(i = 0;i<size;i++)
	{
		bitvec[(Array[i]/32)][(Array[i]%32)] = 1;
	}
	for(i = 0;i<randnum;i++)
	{
		if(bitvec[(i/32)][(i%32)] == 1)
		{
			Array[temp] = i;
			temp++;
		}
	}
	delete [] bitvec;
}


void main()
{
	long size;
	long temp = 0;
	long randnum;
	ofstream out;
	char b[255];
	cout<<"How many.."<<endl;
	cin>>size;
	cout<<"0 to lim.."<<endl;
	cin>>randnum;

	long *Array = new long[size];
	RandArray(Array,size,randnum);

	cout<<"input filename to store the inputdata.."<<endl;
	cin>>b;
	out.open(b,ios::out);
	out<<"Total Number..."<<size<<endl;
	for(long i = 0;i<size;i++)
	{
		out<<Array[i]<<" ";
	}
	out<<endl;
	cout<<endl;
	double start,end;

	start = (double)clock();

	BitSort(Array,size,temp,randnum);
	
	end = (double)clock();

	cout<<"Time elapse..."<<(end-start)<<"ms"<<endl;
	cout<<endl;
	out<<"Time elapse..."<<(end-start)<<"ms"<<endl;
	out<<endl;

	cout<<"input filename to store the outputdata.."<<endl;
	cin>>b;
	for(i = 0;i<temp;i++)
	{
		out<<Array[i]<<" ";
	}
	out.close();
	delete []Array;
}