🕳挖坑法：

挖坑法其实和hoare版本差不了太多 只是形式上有点差别

① 我们首先记录keyi的位置为 坑🕳

② 右边的先走(这里和hoare版本那里一样 先走的一方与keyi 相对) 找小 把数据填到 坑🕳 的位置上 让后当前小的数据(汽车)的位置设为新的 坑位🕳

③ 左边的再走 也是一样的道理 每次挪动数据 都要更新坑位🕳

④ 相遇的位置和坑的位置相同 坑的位置一直都在停留等待的那一方

 我们的 挖坑法🕳 与 hoare版本在 数据移动上 是不一样的 hoare版本是两个数据交换(使用swap函数) 我们的 挖坑法🕳 不一样的是 这个是覆盖 我们首先记录keyi的值 直到最后再把它放在它该有的位子

大家思考一下 这个和hoare版本哪一个会更好一点呢？

其实都差不多 哈哈哈 区别并不大 硬要说有什么区别的话 ：可能就是我们的挖坑法更好理解了把 我们不用太去关心为什么相遇的位置该是keyi等等的问题

  我们只用知道 左边做keyi为坑🕳 那我们就应该找一个小的数放过去 所以我们右边的汽车先走找小填过去 此时的坑🕳更新为靠近右边的位置那我左边的摩托不就是要找个大的数填入过去嘛 最后相遇了 相遇了的位置左右两边 一边大 一边小 此时把keyi放进去不就正好满足条件了嘛 

    int keyi = a[left];
  int pit = left;
  while (left < right)
  {
    while (left < right && a[right] >= keyi)
    {
      right--;
    }
    a[pit] = a[right];
    pit = right;
    while (left < right && a[left] <= keyi)
    {
      left++;
    }
    a[pit] = a[left];
    pit = left;
  }
  a[pit] = keyi;

注意：两个版本的时间复杂度都是O(N)

前后指针法：

这个方法较之前的两种方法 可能有点难理解一些

大家看明白这个动图了嘛 思路很简单：

① 我们的cur往前面走 找小

② 找到 ++prev 交换prev和cur的值

其实总的来讲就是我们把那些小的数往左边移动 大的数又往右边推  而夹在他们中间的数都是大于keyi的数

int PartSort3(int* a, int left, int right)
{
  int prev, cur;
  int keyi = left;
  prev = left;
  cur = left + 1;
  while (cur <= right)
  {
    if (a[cur] <= a[keyi] && a[++prev] != a[cur])//附加的判断条件 意思是我的prev和cur中
    {                                            //间得有值才让交换
      swap(a + prev, a + cur);
    }
    cur++;
  }
  swap(a + keyi, a + prev);
  return prev;
}

咋们这里的小于等于 可以没有 等于 因为相等的数 在左 在右 都是不影响的

咋们这里的限制条件： 只有小于了 并且++prev后不等于cur(就是prev不紧跟在cur后面) 才交换  就是不用自己交换自己了

如果你设置的keyi是在右边 那么我们cur就应该从第一个位置开始遍历 而prev是始终都在cur的前面的 所以 cur=left，prev=left-1；

遍历的时候最右边的数据作为 keyi 就不用去遍历它了 所以我们cur遍历到最后一个数据时 就可以结束了

还有一点要注意 我们cur与prev之间的是比keyi大的数 而keyi的位置又在右边是要放一个大的数 所以我们最后的 prev 还要再加加一次 这样才是一个大于keyi的数放过去

快排的时间复杂度：

我们这样快速排序的几个版本就说完了  现在我们来想想快排的时间复杂度 又会是多少呢？

最坏的情况其实还是存在的 就好像我们的现在的数组是已经有序的了 或者是接近有序的了 现在我们选择 最左 或 最右 的话就又可能选到 最大最小 的数了 而且这种最坏的情况是非常危险的 应为一旦数据过大 就会栈溢出了

那针对这种情况我们 该怎么解决呢 不然我们的快排在这方面就太拉了

其实很简单 就是改变我们选keyi的方式就可以了 我们之前是直接选择最左最右 现在我们不那么做了  我们再 左-中-右 选一个

    int tmp = CheckMidKey(a, (right - left + 1) >> 1, left, right);
    swap(a + left, a + tmp);

我们依旧还是选择左边做 keyi 只不过找到tmp 后把tmp的值和当前left的值换一下不就可以了嘛 此时left就是我们想要的数了

我们此时三数取中：

int CheckMidKey(int* a, int mid, int left, int right)
{
  if (a[mid] < a[right])
  {
    if (a[mid] > a[left])
    {
      return mid;
    }
    else if (a[right] < a[left])
    {
      return right;
    }
    else
    {
      return left;
    }
  }
  else//a[mid]>a[right]
  {
    if (a[mid] < a[left])
    {
      return mid;
    }
    else if (a[right] > a[left])
    {
      return right;
    }
    else
    {
      return left;
    }
  }
}

小区间优化：

对于快排的优化 还不止这一个

小区间优化： 就是当我们递归到数据已经不那么多的时候就不用递归了 直接用其他的排序来解决 因为我们数据很多时 我们递归可以很好的提高效率 毕竟时O(N*logN) 但是当我们数据变少了的时候 这个效率的提高就没那么明显了

好比我们现在一个区间只有5个数据了

所以我们采用小区间优化的话 会消去很多次的递归调用

void QuickSort(int* a, int left, int right)
{
  if (left >= right) return;
  if (right - left + 1<= 10)
  {
    InsertSort(a + left, right - left + 1);
  }
  int keyi = PartSort2(a, left, right);
  QuickSort(a, left, keyi - 1);
  QuickSort(a, keyi + 1, right);
}

right-left 加1 是因为我们的left和 right 都是下标 下标是从0开始的所以加 1

我么的插入排序 的其实位置 是 a+left 因为区间又不一定是从头开始的 也可能是keyi右边的数 就是从当前 left 的位置开始的