//快排序的平均时间复杂度为O(nlgn)

//最坏时间复杂度为O(n^2)

//空间复杂度为O(logn), 递归造成的


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

#define ARRAY_SIZE 10

int partitionArray(int* sortArray, int st, int end)
{
  int i, j, temp;
  j = st+1; // j is from st+1 through end

  i = st;    // i is the exact one before any elements larger than pivot

  for (;j<=end;j++)
    if (*(sortArray+j)<=*(sortArray+st))
    {
      i++;
      if (i!=j)
      {
        temp = *(sortArray+i);
        *(sortArray+i) = *(sortArray+j);
        *(sortArray+j) = temp;
      }
    }
  temp = *(sortArray+i);
  *(sortArray+i) = *(sortArray+st);
  *(sortArray+st) = temp;
  return i;
}


void qSort(int* sortArray, int st, int end)
{
  int pivot;
  if (st<end)
  {
    pivot = partitionArray(sortArray, st, end);
    qSort(sortArray, st, pivot-1);
    qSort(sortArray, pivot+1, end);
  }
  
}



int main()
{
  int sortArray[ARRAY_SIZE]={30, 29, 45, 33, 21, 3, 108, 75, 99, 66};
  int i;
  qSort(sortArray, 0, 9);
  for(i=0;i<10;i++)
    printf("%d ", sortArray[i]);
  printf("\n");
}