paixu.cpp

这是几种排序的运算时间的测试

#include<stdlib.h> 
#include<stdio.h> 
#include<time.h> 
#include<iostream.h>

#define datatype int 
#define CLOCK_PER_SEC 1000

clock_t tstart=0;//time begining
void Settime()
{
tstart=clock();
}//开始的时间
double Gettime()  //所花时间
{
return (double)((double)clock()-(double)tstart)/(double)CLOCK_PER_SEC;
}

void swap(int* a,int* b){
int x;
x=*a;
*a=*b;
*b=x;
}

void SelectSort(datatype R[],int n) 
{ 
int i,k,j; 

Settime();
for(i=1;i<n;i++) 
{ 
k=i; 
for(j=i+1;j<=n;j++) 
if(R[j]<R[k]) 
k=j; 
if(i!=k) 
{ 
R[0]=R[k]; 
R[k]=R[i]; 
R[i]=R[0]; 
} 
} 
} 


void BubbleSort(datatype R[],int n) 
{ 
int i,j; 

int swap; 
Settime();
for(i=1;i<=n-1;i++) 
{ 
swap=0; 
for(j=1;j<=n-i;j++) 

if(R[j]>R[j+1]) 
{ 
R[0]=R[j]; 
R[j]=R[j+1]; 
R[j+1]=R[0]; 
//swap=1; 
} 
//if(swap==0)break; 
} 
} 

void D_InsertSort(datatype R[],int n) 
{ 
int i,j; 

Settime();
for(i=2;i<=n;i++) 
//if(R[i].key<R[i-1].key) 
if(R[i]<R[i-1]) 
{ 
R[0]=R[i]; 
//for(j=i-1;R[0].key<R[j].key;j--) 
for(j=i-1;R[0]<R[j];j--) 
R[j+1]=R[j]; 
R[j+1]=R[0]; 
} 
} 


void inssort2(datatype R[],int n)
{
	int temp=0;
	int j=0;
	for(int i=1;i<n;i++)
		for(int j=i;(j<n)&&(R[j]<R[j-1]);j--)
		R[j+1]=R[j];
		R[j+1]=R[0];
//        swap(&R[j],&R[j-k]);

}
void ShellSort(datatype R[],int n){
	Settime();
	for(int i=n/2;i>2;i/=2){
		for(int j=0;j<i;j++){
inssort2(&R[j],n-j);
inssort2(R,n);
		}	
	}
}


int partition(int R[],int p,int r){
int i=p-1,j;
    for(j = p; j < r; j++)
    {
        if(R[j] >= R[r])
        {
            i++;
            swap(&R[i], &R[j]);
        }
    }
    swap(&R[i + 1], &R[r]);
    return i + 1;
}

void qsort(int R[], int p, int r)
{
	Settime();
    int i;
    if(p < r)
    {
        i = partition(R, p, r);
        qsort(R, 0, i - 1);
        qsort(R, i + 1, r);
    }   
}

void mergesort(datatype R[],datatype temp[],int left,int right){
Settime();
int mid=(left+right)/2;
if(left==right)return;
mergesort(R,temp,left,mid);
mergesort(R,temp,mid+1,right);
for(int i=left;i<right;i++)
temp[i]=R[i];
int l1=left;int l2=mid+1;
for(int key=left;key<=right;key++){
if(l1==mid+1)
R[key]=temp[l2++];
else if(l2>right)
R[key]=temp[l1++];
else if(temp[l1]<temp[l2])
R[key]=temp[l1++];
else R[key]=temp[l2++];
}
}

void main() 
{ 
datatype R[10001]={0};
datatype temp[10001]={0};
int i; 

//randomize(); 
srand((unsigned)time(NULL)); 
for(i=1;i<=10000;i++) 
{ 
R[i]=rand()%100; 
//printf("%6d",R[i]); 
} 
printf("\n"); 

cout<<"InsertSort begin...."<<endl;
D_InsertSort(R,10000); 
//printf("the new list is:%6d\n ",R(i)); 
//printf("the new list is:\n"); 
for(i=1;i<=10000;i++) 
{ 
//printf("%6d",R[i]); 
} 
cout<<"InsertSort end."<<endl;
cout<<"array's size is:"<<"10000"<<endl;
cout<<"The InsertSort's time is: "<<Gettime()<<endl;
printf("\n"); 

cout<<"SelectSort begin...."<<endl;
SelectSort(R,10000); 
//printf("the new list is:%6d\n ",R(i)); 
//printf("the new list is:\n"); 
for(i=1;i<=10000;i++) 
{ 
//printf("%6d",R[i]); 
} 
cout<<"SelectSort end."<<endl;
cout<<"array's size is:"<<"10000"<<endl;
cout<<"The SelectSort's time is: "<<Gettime()<<endl;
printf("\n"); 

cout<<"BubbleSort begin...."<<endl;
BubbleSort(R,10000); 
//printf("the new list is:%6d\n ",R(i)); 
//printf("the new list is:\n"); 
for(i=1;i<=10000;i++) 
{ 
//printf("%6d",R[i]); 
}/**/ 
cout<<"BubbleSort end."<<endl;
cout<<"array's size is:"<<"10000"<<endl;
cout<<"The BubbleSort's time is: "<<Gettime()<<endl;
printf("\n"); 
//getchar(); 

cout<<"ShellSort begin...."<<endl;
ShellSort(R,10000); 
//printf("the new list is:%6d\n ",R(i)); 
//printf("the new list is:\n"); 
for(i=1;i<=1000;i++) 
{ 
//printf("%6d",R[i]); 
} 
cout<<"ShellSort end."<<endl;
cout<<"array's size is:"<<"10000"<<endl;
cout<<"The ShellSort's time is: "<<Gettime()<<endl;
printf("\n");

cout<<"qsort begin...."<<endl;
qsort(R,0,6500);
//for(i=1;i<=10000;i++) {}
cout<<"qsort end."<<endl;
cout<<"array's size is:"<<"6500"<<endl;
cout<<"The qsort's time is: "<<Gettime()<<endl;
/*for(i=1;i<=1000;i++) 
{ 
printf("%6d",R[i]); 
}*/
printf("\n");
//getchar(); 

cout<<"mergesort begin...."<<endl;
mergesort(R,temp,0,10);
cout<<"mergesort end."<<endl;
cout<<"array's size is:"<<"10"<<endl;
cout<<"The mergesort's time is: "<<Gettime()<<endl;
printf("\n");
getchar(); 
}