#define push(a,n) a[--a[0]]=n
#define pop(a,n) n=a[a[0]++]
#define SWAP(a,b) {int temp=a;a=b;b=temp;}
#include <stdio.h>
#include <cstring>
int log2(int n){
int count=0;
while(n){
count++;
n >>=1;
}
return count;
}
template<typename T>
int partionsort(T *seq,int start,int end){
if(0==seq||start>=end) return -1;
int i=start,j=end;
while(i<j){
while(i<=end&&seq[i]<=seq[start]) i++;
while(j>=start&&seq[j]>seq[start])j--;
if(i<j)
SWAP(seq[i],seq[j]);
}
SWAP(seq[start],seq[j]);
return j;
}
template<typename T>
void mquicksort(T * seq,int start,int end){
if(0==seq||start>=end) return ;
int stack_size=end-start+1;
unsigned char *mstack=new unsigned char[(stack_size+2)];//用于存放轴值
memset(mstack,0,(stack_size+2)*sizeof(char));
mstack[0]=stack_size+1;
int h=start,r=end+1;
while(h<=end){
while(h<r){
push(mstack,r);
r=partionsort<T>(seq,h,r-1);
}
pop(mstack,r);
if((r-h)==1){
h=r+1;
pop(mstack,r);
while(h==r) pop(mstack,r);
}
else
h++;
}
}
void main(){
//int a[]={5,3,2,9,6,1,4,8,7};
//int a[]={9,8,9,7,6,2,5,4,7,3,2,1};
//int a[]={1,2,3,4,5,6,7,8,9};
//int a[]={9,8,7,6,5,4,3,2,1};
int a[]={9,9,8,8,7,7,6,6,5,5,4,4,3,3,2,2,1,1};
mquicksort<int>(a,0,sizeof(a)/sizeof(int)-1);
for(int i = 0; i < sizeof(a)/sizeof(int); ++i)
{
printf("%d ", a[i]);
}
getchar();
}