【挖坑&前后指针版】快速排序（3）

在前面我们基于hoare的思想实现了hoare版本的快速排序，但是我们发现hoare版本的快排，易错点太多也不是那么容易理解，所以基于hoare的思想有创新了挖坑版的快排&前后指针版的快排。不同版本的单趟快排，时间复杂度都是O（N）

❗❗❗❗注意会有题目询问单趟排序的结果。hoare版&挖坑版&前后指针版的快排单趟结果都可能不一样，看清楚题目的单趟排序使用的是什么版本的快排。

挖坑版

整体思路

• 和hoare思想雷同，但是增加了两个变量，使其更易理解。
• 一个key用来存储key值
• 一个pits用来表示坑位，用于数据覆盖
• ❗❗重点在覆盖

1. 设置变量key存储key值
2. 设置left 找大，right找小
3. 设置坑位（元素小标）从begin(left)开始
4. right先走，找到小值，覆盖左边坑位，坑位转移到right
5. left再走，找到大值，覆盖右边坑位，坑位转移到left
6. left和right相遇，用key值填坑，坑位就是keyi。

易错点

• 坑位是元素下标
• key是最左边的值，则right先走
• key是最右边的值，则left先走
• 下标和数值对应清晰
• 及时转移坑位

图解分析

代码实现

//挖坑版
int PartSort2(int* a, int begin, int end)
{
  int left = begin;
  int right = end;
  int key = a[begin];//Key值
  int pits = begin;//坑位
  while (left < right)
  {
    //右边先走 找小
    while (left < right && a[right] >= key)
    {
      right--;
    }
    a[pits] = a[right];
    pits = right;
    //左边走找大
    while (left < right && a[left] <= key)
    {
      left++;
    }
    a[pits] = a[left];
    pits = left;
  }
  a[pits] = key;
  return pits;
  //[begin ,pits-1] pits [pits+1,end]
}
void QuickSort(int* a, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
  int keyi = PartSort2(a, begin, end);
  QuickSort(a, begin, keyi - 1);
  QuickSort(a, keyi + 1, end);
}

前后指针版

整体思路

• 整个思路就是类似把大于>key的值类似推箱子往后推
• ❗❗重点在交换

• cur从begin+1的位置开始走，遇到>key的值过掉，cur++
• cur遇到<key的值

1. 与前面prev++之后
2. 交换
3. prev所在的值又变成<key的值了

• prev从begin开始走，prev所在的值只有两种情况

1. a[prev]=a[keyi]
2. a[prev] <a[keyi]

• prev++ 之后的值是cur过掉的值，也就是>key的值

• 两种交换情况

1. 自己和自己交换
2. >key的值和<key的值交换

• 情况1：cur没有遇到比key大的，prev紧跟cur，小与小交换（自己和自己交换）
• 情况2：cur遇到比key大的数值：prev与cur中间隔开了，中间隔开的数值就是比key大的数值，当cur遇到比key小的数值，就可以与这些数值交换，达到一个比key小的数值在前面，大的数值在后面的效果。

图解分析

代码实现

//前后指针版
int PartSort3(int* a, int begin, int end)
{
  int cur = begin + 1;
  int prev = begin;
  int keyi = begin;
  while (cur <= end)
  {
    if (a[cur] > a[keyi])
    {
      cur++;
    }
    else//<=
    {
      prev++;
      Swap(&a[prev], &a[cur]);
      cur++;
    }
  }
  //prev左边比key小 ，右边比key大
  Swap(&a[prev], &a[keyi]);
    keyi=prev;
  return keyi;
}
void QuickSort(int* a, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
  int keyi = PartSort3(a, begin, end);
  QuickSort(a, begin, keyi - 1);
  QuickSort(a, keyi + 1, end);
}

🙂感谢大家的阅读，若有错误和不足，欢迎指正。下篇非递归实现快速排序。