quicksort.cpp

c语言数据结构源代码（全）相当经典

//QuickSort.cpp
//快速排序
# include <iostream.h>
# include <conio.h>

# define MAXSIZE 20
typedef int RedType;

typedef struct					//定义 structure
{   RedType	r[MAXSIZE+1];
    int length;
}SqList;

int  Partition(SqList &L,int low,int high)	//Partition() 子函数
{  int pivotkey;
   L.r[0]=L.r[low];			//用子表的第一个记录作"枢纽"记录
   pivotkey=L.r[low];		//pivotkey是枢纽的记录关键字
   while(low<high)			//从表的两端交替地向中间扫描
      {  while(low<high&&L.r[high]>=pivotkey)
	    --high;
	 L.r[low]=L.r[high];	//比"枢纽"小的记录移到底端
	 while(low<high&&L.r[low]<=pivotkey)
	    ++low;				
	 L.r[high]=L.r[low];	//比"枢纽"大的记录移到高端
      }
   L.r[low]=L.r[0];			//"枢纽"记录到位
   return (low);			//返回"枢纽"位置
} //Partition() end

void Qsort(SqList &L,int low,int high)	//Qsort() sub-function
{  int pivotloc;
   if(low<high)					//长度大于1
   {  pivotloc=Partition(L,low,high);
      Qsort(L,low,pivotloc-1);
      Qsort(L,pivotloc+1,high);
   }
}

void QuickSort(SqList &L)		//QuickSort() 子函数
{  Qsort(L,1,L.length);			//调用 Qsort()
}

void main()						//main() 函数
{  int i;
   SqList L;
   cout<<endl<<endl<<"QuickSort.cpp";
   cout<<endl<<"============="<<endl;
   cout<<endl<<"Please input the length of SqList (eg,5): ";
   cin>>L.length;
   for(i=1;i<=L.length;++i)
   {   cout<<"Please input the "<<i<<"th element of SqList (eg,58): ";
       cin>>L.r[i];
   }
   cout<<endl<<"The disordered : ";		//排序之前的线性表
   for(i=1;i<=L.length;i++)
       cout<<L.r[i]<<"  ";
   QuickSort(L);				//调用 QuickSort()
   cout<<endl<<"The sorted     : ";		//排序之后的线性表
   for(i=1;i<=L.length;i++)
     cout<<L.r[i]<<"  ";
   cout<<endl<<endl<<"...OK!...";
   getch();
} //main() end