main.cpp

分别用快速排序和分治算法对随机产生的200个数进行排序

#include"prediction.h"


int Partition(int Array[],int low,int high)
{	int pivot=Array[low];
	while(low<high)
	{	while(low<high&&Array[high]>=pivot)
			high--;
		Array[low]=Array[high];
		while(low<high&&Array[low]<=pivot)
			low++;
		Array[high]=Array[low];
	}
	Array[low]=pivot;
	return low;
}

//            ________
//___________|快速排序|___________
void QuickSort(int Array[],int low,int high)
{	int Pivotlocation;
	if(low<high)
	{	Pivotlocation=Partition(Array,low,high);
		QuickSort(Array,low,Pivotlocation-1);
		QuickSort(Array,Pivotlocation+1,high);
	}
}


void main()
{	int A[MAX],B[MAX],S1[MAX],S2[MAX];
	int i,j,K,k,M,m1,m2;

	//生成随机数
	for(i=0;i<MAX;i++)
	{	A[i]=rand()%1000;
		for(j=0;i!=0&&j<i;j++)
			if(A[j]==A[i])//判断是否有重复
			{	A[i]=rand()%1000;
				j=-1;
			}
		B[i]=A[i];
	}

	for(i=0;i<MAX;i++) 
	{	printf("%6d",A[i]);
		if((i+1)%10==0)	printf("\n");
	}
	printf("\n");


	//快排
	QuickSort(B,0,MAX-1);
	for(i=0;i<MAX;i++)
	{	printf("%6d",B[i]);
		if((i+1)%10==0)	printf("\n");
	}
	printf("Insert the number K:\n");
	scanf("%d",&K);
	printf("第%d小的数是:%d\n\n",K,B[K-1]); 

	//分治
	int upper_limit=1000,num=MAX;
	printf("\nInput one number k:\n");
	scanf("%d",&k);
	printf("第%d小的数是:",k);

	while(num>10)
	{	M=rand()%upper_limit;
		m1=m2=0;
		for(i=0;i<num;i++)
		{	if(A[i]<=M)
			{	S1[m1]=A[i];
				m1++;
			}
			else
			{	S2[m2]=A[i];
				m2++;
			}
		}
		if(k<m1)
		{	num=m1;
			upper_limit=S1[0];
			for(i=0;i<m1;i++)
			{	A[i]=S1[i];
				if(upper_limit<A[i])	upper_limit=A[i];
			}
		}
		else
		{	num=m2;
			upper_limit=S2[0];
			for(i=0;i<m2;i++)
			{	A[i]=S2[i];
				if(upper_limit<A[i])	upper_limit=A[i];
			}
			k-=m1;
		}
	}
	QuickSort(A,0,num-1);
	printf("%d\n",A[k-1]);

}