#include "stdafx.h"
#include "iostream.h"

void swap(int *a,int low,int high);
void QuickSort(int *a,int st,int ed);
void output(int *a,int low,int high);

void swap(int *a,int low,int high)
{
 int temp=a[low];
 a[low]=a[high];
 a[high]=temp;
}

void QuickSort(int *a,int st,int ed)
{
 int balance=(a[st]+a[ed])/2;
 int low=st;
 int high=ed;
 while(low<high)
 {
   while(a[high]>=balance)  high--;    
   while(a[low]<=balance) low++;
   if(low<high)
     swap(a,low,high);
   if(high==st-1)      
   /*考慮特殊情況，當balance的值為最小值時high會滑出當前st-ed的
     范圍變為st-1,此時僅當a[st]>a[ed]時才才需要交換，比如a{0,1},
     因為while的的循環條件以及下面low和high的值要交換，將low和high
     的值顛倒*/
   {  
     if(a[st]>a[ed]) 
       swap(a,st,ed);      
     high=st; 
     low=st+1;                
   }
   //output(a,low,high);
 }    
 int t=low;
 low=high;
 high=t;        
 if(low>=st+1) 
   QuickSort(a,st,low);
 if(high<=ed-1)
   QuickSort(a,high,ed);  
}

void output(int *a,int low,int high)
{
 for(int i=low;i<=high;i++)
   cout<<a[i]<<" ";
 cout<<endl;  
}

void main()
{
 int arr[15]={1111,4,3,45,454,2,4,56,6,34,1,231,45,63,0};  
 QuickSort(arr,0,14);  
 output(arr,0,14);
}