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

//单趟快排(挖坑版本)
int Partion2(int* a, int left, int right)
{
  //三数取中--面对有序的情况不会栈溢出(key不会选到最大或者最小的数)
  int mini = GetMidIndex(a, left, right);
  swap(&a[left], &a[mini]);
  int key = a[left];
  int pit = left;//坑位起始位置是基准值的位置
  while (left < right)
  {
    //右边找小,放在左边的坑位中
    while (a[right] >= key && left < right)
    {
      right--;
    }
    a[pit] = a[right];//将找到的值扔进坑位
    pit = right;//自身变成新坑位
    //左边找大,放在右边的坑位中
    while (a[left] <= key && left < right)
    {
      left++;
    }
    a[pit] = a[left];//找到的值扔进坑位
    pit = left;//自己变成新坑位
  }
  a[pit] = key;//最终将相遇时的坑位给上最开始记录的key值
  return pit;//返回基准值(或者叫坑位)的位置,方便递归
}

void QuickSort(int* a, int left, int right)
{
  if (left >= right)
  {
    return;
  }
  int key = Partion2(a, left, right);
  QuickSort(a, left, key - 1);//递归左子序列
  QuickSort(a, key + 1, right);//递归右子序列
}

int a[10]={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 QuickSort(int* a, int left, int right)
{
  if (left >= right)
  {
    return;
  }
  int key = Partion3(a, left, right);
  QuickSort(a, left, key - 1);
  QuickSort(a, key + 1, right);
}