main.cpp

本程序实现了通常我们所用的各种排序算法

#include <cmath>
#include <fstream>
#include <time.h>
#include <string>
#include  <iostream>
#include "getTime.h"
#include <vector>
#include <cstddef>
#define  _WRITE_
#define MAX_NUM 32768
#define LASTINT_TIME 60
int FileNum=0;
size_t times=0;	
void CreateData(vector<int> &A,int DataLength)
{	
	for (long i=0 ; i !=DataLength+1 ; ++i)
		A.push_back(rand());
}
void Write(vector<int>A,string fn)
{	
	string file="Temp\\"+fn;
	wchar_t   *   fileN  ;
	fileN   =   new   wchar_t[file.size()];   
	swprintf(fileN,L"%S",file.c_str());  
	ofstream tempFile(fileN);
	for (long i =0 ; i< A.size() ; ++i)
		tempFile<<A[i]<<endl;
	tempFile.close();
	tempFile.clear();
}
void Insertion_Sort(vector<int>  A )
{
	if(times==0)
		cout<<"Insertion sort..."<<endl;
	int temp;
	long i;
	for (long j=1 ; j !=A.size() ;  ++j  )
	{
		temp= A[j];
		i=j-1;
		while (( i>=0)&&(A[i]>temp))
		{
			A[i+1]=A[i];
			i=i-1;
		}
		A[i+1]=temp;
	}
#ifdef  _WRITE_
	if(times==0&&FileNum==4)
		Write(A,"Insertion_Sort_4.txt");
#endif
}
long Partition(vector<int> &A,long p,long r)
{
	int x,temp;
	x=A[r];
	long i=p-1;
	for (long j =p ;j< r ; ++j )
		if (A[j]<x)
		{
			i+=1;
			temp=A[i];
			A[i]=A[j];
			A[j]=temp;
		}
	temp=A[i+1];
	A[i+1]=A[r];
	A[r]=temp;
	return (i+1);
}
void Quick_Sort(vector<int> &A,long p,long r,long DataLength)
{
	if (times==0&&p==0&&r==DataLength)
		cout<<"Quick sort..."<<endl;
	if (p<r)
	{
		long q=Partition(A,p,r);
		Quick_Sort(A,p,q-1,DataLength);
		Quick_Sort(A,q+1,r,DataLength);
	}
#ifdef  _WRITE_
	if (times==0&&p==0&&r==DataLength&&FileNum==4)
		Write(A,"Quick_Sort_4.txt");	
#endif
}

void Counting_Sort(vector<int> A)
{
	if(times==0)
		cout<<"Counting sort..."<<endl;
	vector<long> C;
	for(long i =0 ; i<=MAX_NUM ; ++i )
		C.push_back(0);
	
	vector<int> B;
	for (long i=0; i<A.size();i++)
		B.push_back(0);
	
	for (long j=0 ; j <A.size(); ++j)
		C[A[j]]=C[A[j]]+1;
	
	for (long i =1 ; i<=MAX_NUM; ++i )
		C[i]=C[i]+C[i-1];

	for (long j=A.size()-1; j>=0; --j )
	{			
		B[C[A[j]]-1]=A[j];
		C[A[j]]=C[A[j]]-1;		
	}		
#ifdef  _WRITE_
	if(times==0&&FileNum==4)
		Write(B,"Counting_Sort_4.txt");
#endif
}

void Radix_Sort(vector<int> A)
{
	if(times==0)
		cout<<"Radix sort..."<<endl;
	vector<int> C;
	vector<int> B;

	for (long i=0; i<A.size();i++)
		B.push_back(0);

	for(int i =0 ; i<10 ; ++i )
		C.push_back(0);	
	vector<int>D(C);
	vector<int>E(B);

	for ( int k = 0 ; k < 5 ; ++k)
	{	
		for (long j=0 ; j <A.size(); ++j)
		{	
			E[j]=((A[j]%(int)(pow(10.0,k+1)))/( int )(pow(10.0,k)));
			C[E[j]]+=1;			
		}	

		for (int i =1 ; i<10; ++i )
			C[i]+=C[i-1]; 	

		for (long j=A.size()-1; j>=0;--j )
		{			
			B[C[E[j]]-1]=A[j];
			C[E[j]]-=1;
		}	
		A=B;
		C=D;
	}	
#ifdef  _WRITE_
	if(times==0&&FileNum==4)
		Write(A,"Radix_Sort_4.txt");
#endif
}

int main()
{
	srand(time(NULL));
	long DataLength=0;	
	ofstream outFile;	
//	outFile.open("Out\\Out.txt",ios_base::app);
	outFile.open("Out\\Out.txt");
	outFile<<endl<<"☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆  运  行  ☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆☆"<<endl<<endl
				<<" **************************************   华丽的分割线  ************************************** "<<endl;
	vector<int> A,A1;	
	for(int coun=0 ;coun !=9 ;++coun)
	{	
		FileNum=(coun+2)*2;
		DataLength=(1<<FileNum)-1;
		CreateData(A,DataLength);

		cout<<endl<<"Start sorting 2^"<<FileNum<<endl;
		cout<<"Data length : "<<A.size()<<endl<<endl;		
		
		time_t begi,end;		
			
			outFile<<" Insertion_Sort"<<endl<<" Data length : 2^"<<FileNum<<endl<<'\t'<<"Start time : "<<GetTime()<<endl;
			begi=end=clock();
			times=0;
			while (end-begi<LASTINT_TIME)
			{
				Insertion_Sort(A);
				times++;
				end=clock();
			}						
			outFile<<'\t'<<" End time : "<<GetTime()<<endl;			
			outFile<<'\t'<<" Used time : "<<end-begi<<" ms"<<endl;
			outFile<<'\t'<<"Repeat "<<times<<" times .The average time is :"<<(double)(end-begi)/times<<" ms."<<endl<<endl;


			outFile<<" Quick_Sort"<<endl<<" Data length : 2^"<<FileNum<<endl<<'\t'<<"Start time : "<<GetTime()<<endl;
			begi=end=clock();
			times=0;
			while (end-begi<LASTINT_TIME)
			{	
				A1=A;
				Quick_Sort(A1,0,DataLength,DataLength);
				times++;
				A1.clear();
				end=clock();
			}						
			outFile<<'\t'<<" End time : "<<GetTime()<<endl;			
			outFile<<'\t'<<" Used time : "<<end-begi<<" ms"<<endl;
			outFile<<'\t'<<"Repeat "<<times<<" times .The average time is :"<<(double)(end-begi)/times<<" ms."<<endl<<endl;


			outFile<<" Counting_Sort"<<endl<<" Data length : 2^"<<FileNum<<endl<<'\t'<<"Start time : "<<GetTime()<<endl;
			begi=end=clock();
			times=0;
			while (end-begi<LASTINT_TIME)
			{
				Counting_Sort(A);
				times++;
				end=clock();
			}									
			end=clock();
			outFile<<'\t'<<" End time : "<<GetTime()<<endl;			
			outFile<<'\t'<<" Used time : "<<end-begi<<" ms"<<endl;
			outFile<<'\t'<<"Repeat "<<times<<" times .The average time is :"<<(double)(end-begi)/times<<" ms."<<endl<<endl;
	
		
			outFile<<" Radix_Sort"<<endl<<" Data length : 2^"<<FileNum<<endl<<'\t'<<"Start time : "<<GetTime()<<endl;
			begi=end=clock();
			times=0;
			while (end-begi<LASTINT_TIME)
			{
				Radix_Sort(A);
				times++;	
				end=clock();
			}						
			outFile<<'\t'<<" End time : "<<GetTime()<<endl;			
			outFile<<'\t'<<" Used time : "<<end-begi<<" ms"<<endl;
			outFile<<'\t'<<"Repeat "<<times<<" times .The average time is :"<<(double)(end-begi)/times<<" ms."<<endl<<endl;			

		outFile<<endl<<" **************************************   华丽的分割线  ************************************** "<<endl;
		A.clear();	
	}
	outFile.close();
	return 0;	
}