int a[]={6,1,2,7,9,3,4,5,10,8};

//单趟快排(前后指针版本)
int Partion3(int* a, int left, int right)
{
  //三数取中--面对有序的情况不会栈溢出(key不会选到最大或者最小的数)
  int mini = GetMidIndex(a, left, right);
  swap(&a[left], &a[mini]);
  int key = left;
  int prev = left;
  int cur = left + 1;
  while (cur <= right)
  {
    while (a[cur] >= a[key] && cur <= right)//cur指针找小于key的
    {
      ++cur;
    }
    if (cur <= right)
    {
      swap(&a[++prev], &a[cur]);
      cur++;//交换完后,cur要再往后走一步
    }
  }
  swap(&a[key], &a[prev]);// 最后交换prev和key的值
  return prev;//返回基准值的位置,方便下次递归
}

//快速排序(非递归)
void QuickSortNonR(int* a, int left, int right)
{
  ST st;
  StackInit(&st);
  StackPush(&st, left);
  StackPush(&st, right);
  while (!StackEmpty(&st))//当栈不为空时就继续
  {
    int end = StackTop(&st);//将栈顶元素赋值给下标遍历的尾
    StackPop(&st);//删除栈顶元素
    int begin = StackTop(&st);//再将新的栈顶元素给下标遍历的头
    StackPop(&st);//再把这个值删除
    int key = Partion3(a, begin, end);//单趟快排返回基准值对应位置下标
    if (key < end)
    {
      StackPush(&st, key + 1);
      StackPush(&st, end);
    }
    if (begin < key - 1)
    {
      StackPush(&st, begin);
      StackPush(&st, key);
    }
  }
  StackDestroy(&st);
}