快速排序

#include <stdio.h>
#include <stdlib.h>

template <class T>
void
swap(T& a, T& b)
{
  T temp;
  temp=a;
  a=b;
  b=temp;
}

template <class T>
void
partion(T* array, int left, int right)
{
  if(left >= right )
    return;
  int low=left;
  int hight=right-1;
  while(low<=hight){
    while(array[low]<=array[right] && low<=hight){low++;}
    while(array[hight]>array[right] && low<=hight){hight--;}
    if(low<=hight)
      swap(array[low++], array[hight--]);
  }
  swap(array[low], array[right]);
  partion(array, left, low-1);
  partion(array, low+1, right);
}

int
main()
{
  int array[10]={9,2,1,4,5,6,7,8,9,5};
  int len = sizeof(array)/sizeof(int);
  partion(array, 0, len-1);
  for(int i=0;i<len;++i){
    printf("%d ", array[i]);
  }
  printf("\n");
}