quicksort.cpp

熟悉快速排序法的基本思想

 #include<iostream.h>
 #define N 11
 typedef int keytype ;
 typedef int elemtype ;
 typedef struct
 {    keytype key;                  
      elemtype otheritems;            
 }recordtype;                         
 recordtype R[N];
int dividearsort(recordtype R[],int s,int t)
{
	int i,j;
	recordtype temp;
	i=s;  j=t;
	temp=R[s];
	do
	{
		while((R[j].key>=temp.key)&&(i<j))
	    	j--;
		if(i<j)
		{
			R[i]=R[j];
		    i++;
		}
		while((R[i].key<=temp.key)&&(i<j))
			i++;
		if(i<j)
		{
			R[j]=R[i];
			j--;
		}
	}while(i<j);
	R[i]=temp;
	return i;
}
void quicksort(recordtype R[],int s,int t)
{
	int i;
	if(s<t)
	{
		i=dividearsort(R,s,t);
		quicksort(R,s,i-1);
		quicksort(R,i+1,t);
	}
}
void main()
{
	int i;
	cout<<"待排序的数组:";
	for(i=1;i<N;i++)
		cin>>R[i].key;
	int s=1;
	int t=N-1;
	quicksort( R,s,t);
  	cout<<"快速排序后：";
	for(int k=1;k<N;k++)
		cout<<R[k].key<<"  ";
	cout<<endl;
}