//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