quisort.cpp

QUCICKSORT 快速排序算法的时间分析

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

void exchange(long A[],long &i,long &j){
    long x;
	x=i;
	i=j;
	j=x;
}
long Partition(long A[],long p,long r){
    long y,x;
	long i,j;
	x=A[r];
	i=p-1;
	for(j=p;j<r;j++){
		if(A[j]<=x){
			i=i+1;
			y=A[i];
	        A[i]=A[j];
	        A[j]=y;
			//exchange(A,A[i],A[j]);
		}
	}
	y=A[i+1];
	A[i+1]=A[r];
	A[r]=y;
	//exchange(A,A[i+1],A[r]);
	return i+1;
}
void Quicksort(long A[],long p,long r){
    long q;
	if(p<r){
		q=Partition(A,p,r);
	    Quicksort(A,p,q-1);
        Quicksort(A,q+1,r);
	}
}
void main(){
	clock_t start,finish;
	double duration,sum;
	long k,i;
	long AMAX;
    long *A;
	FILE *fp;
	if(!(fp=fopen("temp1.txt","a")))printf("ok\n");
	else printf("no\n");
	AMAX=10000000;
		sum=0;
			printf("%d个数据用时：\n",AMAX); 
		fprintf(fp,"%d个数据用时：\n",AMAX);
		for(i=0;i<10;i++){
			A=new long[AMAX];
	        srand((unsigned)time(NULL));
	        for(k=0;k<AMAX;k++)
		       A[k]=rand();
            start = clock(); 
	        Quicksort(A,0,AMAX-1);
            finish = clock(); 
	        duration = (double)(finish - start) / CLOCKS_PER_SEC;
            fprintf(fp,"%f second ",duration);
			printf("%f second ",duration);
			sum+=duration;
			
		
			delete  []A;
				 
		}
		fprintf(fp,"\n平均用时：%f\n",sum/10);
		
		
	
	 
  
}