快速排序.cpp

快速排序,算法分析与设计第二章分治法思想的快速排序算法实现.

#include"stdio.h"
typedef int DataType;
void swap(DataType *a,DataType *b)
{  
   DataType *t=new DataType(*a);
   *a=*b;
   *b=*t;
}
int partition(DataType a[],int l,int r)
{//排序a[l:r]
	int i=l;	//从左至右的游标
	int j=r+1;  //从右至左的游标
   DataType pivot=a[l];
   if(l>=r)return a[l];
//把左侧>=pivot的元素和右侧<=pivot的元素进行交换
   while(1)  
   {
	 do{//在左侧寻找>=pivot的元素
 	    i=i+1;
	   }while(a[i]<pivot);
	 do{//在右侧寻找<=pivot的元素
        j=j-1;	 
	 }while(a[j]>pivot);
   if(i>=j)
	   break;//未发现交换对象
       swap(&a[i],&a[j]);
      }
//设置pivot
   a[l]=a[j];
   a[j]=pivot;
   return j;
}
void quicksort(DataType a[],int l,int r)
{  int j;
   if(l<r){
   j=partition(a,l,r);
   quicksort(a,l,j-1);
   quicksort(a,j+1,r);}
}
void QuickSort(DataType *a,int n)
{//对a[0:n-1]进行快速排序
   quicksort(a,0,n-1);	
}
void printfsort(DataType *a,int n)
{  int i;
   for(i=0;i<=n-1;i++)
   printf("%4d",a[i]);
   printf("\n");
}
void main()
{ 
   DataType a[10]={5,9,3,1,8,2,7,4,6,10};
   //初始化a[10]
   QuickSort(a,10);
   printfsort(a,10); 
}