sf.cpp

随即算法小课设

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

# define MAX 10001

void values(int num, int A[])
{
	int i;
	srand(unsigned(time(NULL))); 

	for(i=1;i<=num;i++)
	{
        A[i]=rand()%num;  
	}
}

long selectionsort(int num,int A[])
{
	long s=0;
	int i,j,k,temp;
    for(i=1;i<num;i++)
	{
		k=i;
		for(j=i+1;j<=num;j++)
		{
			if(A[j]<A[k])
				k=j;
			s++;
		}
		if(k!=i)
		{
           temp=A[i];
		   A[i]=A[k];
		   A[k]=temp;
		}
	}
	return s;
}

long insertionsort(int num,int A[])
{
	long s=0;
	int i,j;
	int x;
	for(i=2;i<=num;i++)
	{
       x=A[i];
	   j=i-1;
	   while(j>0&&A[j]>x)
	   {
			s++;
			A[j+1]=A[j];
		    j--;
	   }
	   A[j+1]=x;
	}
	return s;
}

long Merge(int A[],int p,int q,int r)
{
     int B[MAX];
	 int s,t,k,i,j;
	 s=p;
	 t=q+1;
	 k=p;
	 long a=0;
	 while(s<=q&&t<=r)
	 {
		 if(A[s]<=A[t])
		 {
			 B[k]=A[s];
		     s=s+1;
		 }
		 else{
		     B[k]=A[t];
			 t=t+1;
		 }
		 k=k+1;
		 a++;
	 }
	 if(s=q+1)
		 for(i=k,j=t;i<=r;i++,j++)
			 B[i]=A[j];
	        else
			 for(i=k,j=s;i<=r;i++,j++)
				 B[i]=A[j];
	 for(i=p;i<=r;i++)
		 A[i]=B[i];
	 return a;
}

long c1=0;
long buttomupsort(int num,int A[])
{
     int s,t,i;
	 t=1;
	 long a=0;
	 while(t<num)
	 {
		 s=t;
		 t=2*s;
		 i=0;
		 while(i+t<=num)
		 {
			 a=Merge(A,i+1,i+s,i+t);
			 c1+=a;
			 i=i+t;
		 }
		 if(i+s<num)
		 {
			 a=Merge(A,i+1,i+s,num);
			 c1+=a;
		 }
	 }
	 return c1;
}

long c3=0;
long mergesort(int m,int num,int A[])
{
    int mid; 
	long a=0;
	 if(m<num)
	 {
         mid=(m+num)/2;
		 mergesort(m,mid,A);
		 mergesort(mid+1,num,A);
		 a=Merge(A,m,mid,num);
		 c3+=a;
	 }
	 return c3;
}

typedef struct rec{
    int rot;
	long s;
}rec;    

rec split(int m,int n,int A[])
{
	int i=m;
	int x=A[m];
	int temp;
	rec a;
	a.s=0;
	for(int j=m+1;j<=n;j++)
	{
		a.s++;
		if(A[j]<=x)
		{
			i=i+1;
			if(i!=j)
			{
               temp=A[i];
			   A[i]=A[j];
			   A[j]=temp;
			}
		}
	}
	temp=A[m];
	A[m]=A[i];
	A[i]=temp;
	a.rot=i;
	return a;
}

long c2=0;       //全局变量，可以不为零的连续计数
long quicksort(int m,int num,int A[])
{
    rec a;	
	if(m<num)
	{
		a=split(m,num,A);
		c2+=a.s;
		quicksort(m,a.rot-1,A);
		quicksort(a.rot+1,num,A);
	}
	return c2;
}


void main(void)
{
	int num,i=0;
	int A[MAX];
	cout<<"enter the numbers:"<<endl;
	cin>>num;

	values(num,A);
	long count;
   long sum=0;

/*	for(i=0;i<10;i++)
	{
		count=mergesort(1,num,A);
	    sum+=count;
	}
	count=sum/10;*/
	
//	cout<<count<<endl;

//	values(num,A);
//	count=insertionsort(num,A);
//	cout<<count<<endl;

	count=quicksort(1,num,A);
//    cout<<count<<endl;

  //	count=buttomupsort(num,A);
 //   cout<<count<<endl;
    
//	count=selectionsort(num,A);
//	count=mergesort(1,num,A);
    cout<<count<<endl;
}