#include <stdio.h>
#include <iostream.h>

#define MAX 255
int R[MAX];

int Partition(int i,int j)
{/* 調用Partition(R，low，high)時，對R[low..high]做劃分，*/
     /* 并返回基準記錄的位置 */
      int pivot=R[i]; /* 用區間的第1個記錄作為基準 */
      while(i<j){ /* 從區間兩端交替向中間掃描，直至i=j為止 */
        while(i<j&&R[j]>=pivot) /* pivot相當于在位置i上 */
          j--;  /* 從右向左掃描，查找第1個關鍵字小于pivot.key的記錄R[j] */
        if(i<j) /* 表示找到的R[j]的關鍵字<pivot.key  */
            R[i++]=R[j]; /* 相當于交換R[i]和R[j]，交換后i指針加1 */
        while(i<j&&R[i]<=pivot) /* pivot相當于在位置j上*/
            i++; /* 從左向右掃描，查找第1個關鍵字大于pivot.key的記錄R[i] */
        if(i<j) /* 表示找到了R[i]，使R[i].key>pivot.key */
            R[j--]=R[i]; /* 相當于交換R[i]和R[j]，交換后j指針減1 */
       } /* endwhile */
      R[i]=pivot; /* 基準記錄已被最后定位*/
      return i;
}  

void Quick_Sort(int low,int high)
{  
     int pivotpos; /* 劃分后的基準記錄的位置 */
     if(low<high){ 
		pivotpos=Partition(low,high); /* 對R[low..high]做劃分 */
        Quick_Sort(low,pivotpos-1); /* 對左區間遞歸排序 */
        Quick_Sort(pivotpos+1,high); /* 對右區間遞歸排序 */
      }
}  


void main()
{
	int i,n;
 
	cout << "Please input total element number of the sequence:" ;
	cin >> n;
	if(n<=0||n>MAX)
	{
		cout << "n must more than 0 and less than" << MAX;
	}
	cout << "Please input the elements one by one:" << endl;
	for(i=1;i<=n;i++)
		cin >> R[i];
	cout << "The sequence you input is:";
	for(i=1;i<=n;i++)
		cout << "   " << R[i];
	Quick_Sort(1,n);//快速排序
	cout  << endl << endl;
	cout << "The sequence after bubble_sort is:";
	for(i=1;i<=n;i++)
		cout << "   " <<  R[i];
	cout << endl << endl;
	return;
	
}