int PartSort1(int* a, int left, int right)
{
  //整体思路是先让right先走找到一个比a[keyi]小的数然后等待left找到比a[keyi]大的数
  //然后交换即可.
  int keyi = left;//不能给零,因为每次递归的时候我们都要通过不同的left来操作.
  while (left < right)
  {
    if (a[right] < a[keyi])//先让right先走为了保证left和right听的位
    {
      while (left < right)
      {
        if (a[left] > a[keyi])
        {
          Swap(&a[left], &a[right]);
          break;//记得break因为我们要先right走.
        }
        left++;
      }
    }
    right--;
  }
  Swap(&a[left], &a[keyi]);//最后记得把keyi的换位完成
  return left;
}
void QuickSort(int* a, int left, int right)
{
  if (left > right)
  {
    return;
  }
  int keyi = PartSort1(a, left, right);
  QuickSort(a, left, keyi - 1);
  QuickSort(a, keyi + 1, right);
}

int PartSort2(int* a, int left, int right)
{
  //坑法可以不用让right先走了,更加便于理解=.=
  //下面的思路以升序为例
  //整体思路:用一个变量保存keyi的位置的变量并把keyi的位置当做坑位,当right(以此为例)
  //的找到比a[keyi]大的值的时候直接塞到坑的位置,然后让right当做坑,用left来找....
  int keyi = left;
  int tmp = a[keyi];
  int pit = leyi;//上面tmp保存那个值就先用那个地方当坑使.
  while (left < right)
  {
  if (a[right] < a[keyi])
  {
    a[pit] = a[right];
    pit = right;//右边搞完了,走左边
    while (left < right)
    {
    if (a[left] > a[keyi])
    {
      a[pit] = a[left];
      pit = left;
      break;//break记得弄因为我们这时又把坑位给到了left的位置应该走right了
    }
    left++;
    }
  }
  right--;
  }
  a[left] = tmp;
  return left;
}