shiyan6.cpp

本程序比较各种排序算法的优劣（包括快速比较

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/timeb.h>
#define  SSIZE 100000               
#define MAX 32767
#define NCOL 10
#define BUFFERSIZE 128
typedef struct Node {
	int	num;
	struct Node *next;
} Node,*pNode;

typedef int DataType[SSIZE+2];
DataType data;
DataType data2;

long compcount;
long shiftcount;
int swapped;
int size;

timeb StartTime,EndTime;



void printfd(){
	int i;
	
	
	printf(" \n comparisonCount:%6u\n shiftCount:%6u\n",compcount,shiftcount);
    
	printf("\n重排后的数据如下:\n");       
    
    for(i=1;i<=size;i++)
	 { printf("%6u",data[i]);if(i%NCOL==0)
	printf("\n");}
}
void BeforeSort(){ //初始化
	int i;
	for(i=0;i<=size;i++)
		data[i]=data2[i];
	compcount=shiftcount=0;}
int Less(int i,int j){
	compcount++;
	if (data[i]<data[j]) return 1;
    else return 0;
}
void Swap(int i,int j){
    data[0]=data[j];
    data[j]=data[i];
    data[i]=data[0];
	shiftcount+=3;}
void Shift(int i,int j){
	data[j]=data[i];
	shiftcount++;
}
/*void WriteToFile(char* FileName,int data,long SIZE)
{
	FILE *fp;
	fp=fopen(FileName,"w");
	if(fp==NULL)
	{
		printf("建立文件失败");
		exit(0);
	}
	for(int i=1;i<=SIZE;i++)
	{
		char buffer[BUFFERSIZE];
		itoa(data[i],buffer,10);
		int len;
		len=strlen(buffer);
		buffer[len++]='\n';
		fwrite(buffer,sizeof(char),len,fp);
	}
	fclose(fp);
}*/

void printt(){printf("nihao\n");}
void Merge(DataType data,DataType data3,int i,int m,int n){
	int j,k;
	for(j=m+1,k=i;i<=m&&j<=n;++k)
	{   if(Less(i,j)) data3[k]=data[i++];
	    else data3[k]=data[j++];
		shiftcount++;
	}
	if (i<=m){
		  for(;k<=n&&i<=m;k++,i++)
		  data3[k]=data[i];
		  shiftcount++;}
	if (j<=n){
		  for(;k<=n&&j<=n;k++,j++)
		  data3[k]=data[j];
		  shiftcount++;}
}





int BubbleSort(){        //冒泡排序
	int i;
	BeforeSort();
    do{swapped=0;
    for(i=1;i<=size-1;i++)
		if(Less(i+1,i)){Swap(i,i+1);swapped=1;}}while(swapped);

		printf("\nBubbleSort:");
		
		printfd();
		return 0;
}


int InsertSort(){   //插入排序
	int i,j;
	BeforeSort();
	for(i=2;i<=size;i++){
		Shift(i,0);j=i-1;
		while(Less(0,j)){Shift(j,j+1);j--;}
		Shift(0,j+1);
	}
	
    
		  printf("\nInsertSort:");
		  
		  printfd();
		  return 0;
}
int SelectSort(){//选择排序
	int i,j,min;
	BeforeSort();
	for(i=1;i<=size-1;i++){
		min=i;
		for(j=i+1;j<=size;j++)
			if (Less(j,min))min=j;
			if(i!=min)Swap(i,min);
	}
	
		  printf("\nSelectSort:");
		  
		  printfd();
		  return 0;		 
}
void QSort(int lo,int hi){
	int i,j,m;
	if(lo<hi){
		i=lo;j=hi;m=(lo+hi)/2;
		do{
			while(Less(i,m))i++;
			while(Less(m,j))j--;
			if(i<=j){
				if (m==i)m=j;
				else if(m==j)m=i;
				Swap(i,j);i++;j--;}}while(i<=j); 
				QSort(lo,j);QSort(i,hi);    //i=m+1 j=m-1
	}	
}
int QuickSort(){//快速排序
	
	BeforeSort();
	QSort(1,size);
	
	
		  printf("\nQuickSort:");
		  
		  printfd();
		  return 0;
}
int ShellSort(){// 希尔排序
	int i,h,j;
	BeforeSort();
	i=5;h=1;
	while(i<=size){i=i*2;h=2*h+1;}
	while(h!=0){
		i=h;
		while(i<=size){
			j=i-h;
			while(j>0&&Less(j+h,j)){Swap(j,j+h);j=j-h;}
			i++;
		}
		h=(h-1)/2;}
	printf("\nShellSort:");
	
		  printfd();
		  return 0;
}
void Sift(int left,int right){
	int i,j,finished;
	i=left;j=2*i;Shift(left,0); finished=0;
	Shift(left,size+1);
	while(j<=right&&!finished){
		if(j<right&&!Less(j+1,j))j=j+1;
		if(Less(j,0))finished=1;
		else{Shift(j,i);i=j;j=2*i;}
	}
	Shift(size+1,i);
}
int HeapSort(){//堆排序
	int left,right;
	BeforeSort();
	
	for(left=size/2;left>=1;left--)Sift(left,size);
	for(right=size;right>=2;right--)
	{Swap(1,right);Sift(1,right-1);}
	printf("\nHeapSort:");
	
		  printfd();
		  return 0;
		  
}



int Binsertsort(){//折半插入排序
int i,m,j,low,high;
	BeforeSort();
	for(i=2;i<=size;++i){
	Shift(i,0);
	low=1;high=i-1;
	while(low<=high){
	m=(low+high)/2;
	if(Less(0,m))high=m-1;
	else low =m+1;}
	for(j=i-1;j>=high+1;--j)Shift(j,j+1);
	Shift(0,high+1);}
	printf("\nBinsertsort:");

		  printfd();
		  return 0;

}

void TwowaySort()
{//二路插入排序
	long i,j,k;
	int *b;
	long final=1;
	long first=size;
int *pNum;
BeforeSort();

pNum=data;
	b=(int *)malloc((size+1)*sizeof(int));
	if(pNum[1]>pNum[2])
	{
		b[1]=pNum[1];
		b[size]=pNum[2];shiftcount+=2;compcount++;
	}
	else
	{
		b[size]=pNum[1];
		b[1]=pNum[2];shiftcount+=2;compcount++;
	}
	for(i=3;i<=size;i++)
	{
		if(pNum[i]>=b[1])
		{compcount++;
			for(j=final;pNum[i]<b[j]&&j>0;j--)
			{b[j+1]=b[j];shiftcount+=2;compcount++;}
			b[j+1]=pNum[i];
			final++;shiftcount++;
		}
		else
		{compcount++;
			for(k=first;pNum[i]>=b[k]&&k<=size;k++)
			{	b[k-1]=b[k];shiftcount+=2;compcount++;}
			b[k-1]=pNum[i];
			first--;shiftcount++;
		}
	}
	i=1;
	for(j=first;j<=size;j++)
	{
		pNum[i]=b[j];
		++i;shiftcount++;
	}
	for(j=1;j<=final;j++)
	{
		pNum[i]=b[j];
		++i;shiftcount++;
	}
printf("\nTwowaySort:");
 printfd();


}


void Merge(int *pNum,long h,long u,long v) 
{
	int i=h,j=u+1,k,temp;
	while(i<=u&&j<=v)               
	{
		if(pNum[i]>pNum[j])            
		{compcount++;shiftcount++;
			temp=pNum[j];
			k=j;
			while(i<k)                  
			{
				pNum[k]=pNum[k-1];
				k--;shiftcount++;
			}
			pNum[i]=temp; shiftcount++;               
			j++;
			u++;
		}
		else
		{	i++;compcount++;}
	}
}

void MSort(int *pNum,long n,long l)
{
	int i;
	for(i=0;i+l<=n&&i+2*l<=n;i+=2*l)
		Merge(pNum,i+1,i+l,i+2*l);
	if(i+l<=n)
		Merge(pNum,i+1,i+l,n);
	else
		Merge(pNum,i-2*l+1,i,n);
}

void MergeSort()//归并排序
{int *pNum;

BeforeSort();
pNum=data;
	long l=1;
	while(l<=size)
	{
		MSort(pNum,size,l);
		l*=2;
	}
printf("\nMergeSort:");
 printfd();

}


void Distribute(pNode &head,pNode &tail,pNode *t,pNode *e, int i)
{
	pNode pPre = NULL,pCur = NULL;
	int	temp;
    for(pCur=head; ; pCur=pPre){
		temp=(int)((pCur->num%i)/(i/10));
		if(t[temp]==NULL){t[temp]=e[temp]=pCur;}
		else { e[temp]->next = pCur; e[temp] = pCur; }
		pPre = pCur->next; pCur->next=NULL;
		if ( pCur == tail ) break;
	}
}

void Collect( pNode &head,pNode &tail,pNode *t,pNode *e)
{
	int	i;
	pNode p = NULL;

	head=tail=NULL;
	for(i = 0; i<10; i++) {
		while ( t[i] ) {
			if(head == NULL) {head=tail=t[i]; p=t[i];}
			else { p->next = t[i]; p = tail = t[i]; }
			t[i] = t[i]->next;
		}
		e[i] = NULL;
	}
}

void RadixSort(  )//基数排序
{
	int i;
	pNode head = NULL,tail = NULL,p = NULL;
	pNode t[10], e[10];
     BeforeSort();
	for(i=0; i<10; i++ ) t[i] = e[i] = NULL;
	for (i = 1; i <= size; i++ ) {
		p = new Node;
		if ( i==1 ) { head = tail = p; }
		else { tail -> next = p;
			tail = p;
		}
		p->num = data[i];
	}
	for ( i = 10; i <= 100000; i *= 10 ) {
		Distribute( head, tail, t, e, i );
		Collect( head, tail, t, e );
	}
	for ( i=1,p = head; ; head = p,i++ ) {
		data[i] = head->num;
		if(head==tail) break;
		p = head->next;
		delete head;
	}
	printf("\nRadixSort:");
		
		printfd();
}






void main()
{
int i,n,num;
int select;


do{  	srand((unsigned) time (NULL));
printf("请输入产生随机数个数：\n");
scanf("%d",&size);
printf("请输入随机数最大值：\n");
scanf("%d",&select);
if(select<2||select>MAX)
printf("number is out of range.\n");
printf("排序前数据:\n");
for(n=1;n<=size;)
{
	num=rand();
	num%=select;
	data2[n]=num;
    
	printf("%6u",data2[n]);
	if(n%NCOL==0)
		printf("\n");
	n++;}
/*for(i=1;i<=size;i++)
	{
		data[i]=rand();
	}
	//排序前结果写入文件
	WriteToFile("bfile.txt",data,size);


*/



ftime(&StartTime);
i=BubbleSort();
ftime(&EndTime);
printf("\n耗时%d毫秒\n",EndTime.time*1000-StartTime.time*1000+EndTime.millitm-StartTime.millitm);
//排序后结果写入文件
/*	WriteToFile("aBubblefile.txt",data,size);*/

ftime(&StartTime);
i=InsertSort();
ftime(&EndTime);
printf("\n耗时%d毫秒\n",EndTime.time*1000-StartTime.time*1000+EndTime.millitm-StartTime.millitm);
//排序后结果写入文件
/*	WriteToFile("aInsertSort.txt",data,size);*/
ftime(&StartTime);
i=SelectSort();
ftime(&EndTime);
printf("\n耗时%d毫秒\n",EndTime.time*1000-StartTime.time*1000+EndTime.millitm-StartTime.millitm);
//排序后结果写入文件
/*	WriteToFile("aSelectSort.txt",data,size);*/
ftime(&StartTime);
i=QuickSort();
ftime(&EndTime);
printf("\n耗时%d毫秒\n",EndTime.time*1000-StartTime.time*1000+EndTime.millitm-StartTime.millitm);
//排序后结果写入文件
/*	WriteToFile("aQuickSort.txt",data,size);*/
ftime(&StartTime);
i=ShellSort();
ftime(&EndTime);
printf("\n耗时%d毫秒\n",EndTime.time*1000-StartTime.time*1000+EndTime.millitm-StartTime.millitm);
//排序后结果写入文件
/*	WriteToFile("aShellSort.txt",data,size);*/
ftime(&StartTime);
i=HeapSort();
ftime(&EndTime);
printf("\n耗时%d毫秒\n",EndTime.time*1000-StartTime.time*1000+EndTime.millitm-StartTime.millitm);
//排序后结果写入文件
/*	WriteToFile("aHeapSort.txt",data,size);*/
ftime(&StartTime);
i=Binsertsort();
ftime(&EndTime);
printf("\n耗时%d毫秒\n",EndTime.time*1000-StartTime.time*1000+EndTime.millitm-StartTime.millitm);
//排序后结果写入文件
/*	WriteToFile("aBinsertsort.txt",data,size);*/
ftime(&StartTime);
TwowaySort();
ftime(&EndTime);
printf("\n耗时%d毫秒\n",EndTime.time*1000-StartTime.time*1000+EndTime.millitm-StartTime.millitm);
//排序后结果写入文件
/*	WriteToFile("aTwowaySort.txt",data,size);*/
ftime(&StartTime);
MergeSort();
ftime(&EndTime);
printf("\n耗时%d毫秒\n",EndTime.time*1000-StartTime.time*1000+EndTime.millitm-StartTime.millitm);
//排序后结果写入文件
/*	WriteToFile("aMergeSort.txt",data,size);*/
ftime(&StartTime);
RadixSort();
ftime(&EndTime);
printf("\n耗时%d毫秒\n",EndTime.time*1000-StartTime.time*1000+EndTime.millitm-StartTime.millitm);
//排序后结果写入文件
/*	WriteToFile("aRadixSort.txt",data,size);*/

}while(!i);



}