//快速排序遞歸算法

#include <iostream.h>
#include <stdlib.h>

int QKPass(int r[], int low, int high)
{
	int k0,Pkey=r[low];
	r[0]=r[low];
	while(low<high)
	{
		while(low<high && r[high]>=Pkey) --high;
		k0=r[low];
		r[low]=r[high];
		r[high]=k0;
		while(low<high && r[low]<=Pkey) ++low;
		k0=r[low];
		r[low]=r[high];
		r[high]=k0;
	} //while
	r[low]=r[0];
	return low;  //返回樞軸所在位置
} //QKPass

void QKSort(int r[], int s, int t)
{
	//對(duì)記錄序列L.r[s..t]進(jìn)行快速排序
	if (s<t)
	{
		//長度大于1
		int pos=QKPass(r, s, t);
		//對(duì) L.r[s..t] 進(jìn)行一次劃分
		QKSort(r, s, pos-1);
		//對(duì)低子序列遞歸排序, pos是樞軸位置
		QKSort(r, pos+1, t);  //對(duì)高子序列遞歸排序
	} //if
} //QKSort

void main()
{
	int n;
	int i,*r;
	cout<<"請(qǐng)輸入待排序整數(shù)的個(gè)數(shù)n：";
	cin>>n;
	r=new int[n+1];
	cout<<"請(qǐng)輸入"<<n<<"個(gè)待排序整數(shù)：";
	for(i=1; i<=n; i++){
		cin>>r[i];
	}
	QKSort(r, 1, n);
	cout<<"排序后的整數(shù)序列：";
	for(i=1; i<=n; i++) cout<<r[i]<<" ";
	cout<<endl;
}