2.2.3 前后指针版本

1962年Hoare大神运用双指针算法重新设计了交换排序的单趟排序,并运用分治递归实现代替了嵌套循环实现,完成了交换排序的终极优化

单趟排序算法实现思想:

1.选取arr[left]作为key(key变量作为下标指向key元素)

2.slow初值为left,fast指针从left+1位置开始遍历数组

3.若fast指针找到了比key小的元素,则令slow指针向后走一步,并交换slow和fast指针指向的元素

4.若fast指针找到了比key大的元素,slow指针不动,fast指针继续向后遍历数组

5.重复上述过程直到fast指针完成数组的遍历,最后再将key元素交换到slow最终指向的位置

6.最终从left位置到slow位置的所有元素就是整个数组中比key小的所有元素.

先看动图： 前后指针法的思路：

定义三个变量，prev=begin，cur=begin+1,key=begin，主要使用 cur 来遍历数组。

1.如果cur 指向的元素比key 小，此刻停下来，++prev ，交换调整后的prev 位置和 cur 位置的值，之后 cur++ 。

2.如果cur 指向的元素大于等于key ，cur++ ，其他啥也不干。

3.就这样循环往复，直到cur>end ，此刻交换prev 和 key 位置的值。

当前的 prev 作为新的key ，为分割点。

这里的 prev 和cur 有两种状况：

1.紧跟cur ，这时 a[cur]<a[key] ，它俩同步往后走

2.指向比 key 大的位置的前一个，pprev 和 cur 之间就是 ≥ a [ key ]个值。

每当 a[cur]<a[key] ，cur 位置小于a[key] 的值总是会被推到前面。循环的过程相当于是将小于a[key] 的值往前翻，大于 a[key] 的值往后像“翻跟头”一样推着走。 最后prev 的位置指向比 a[key] 大的位置的前一个，那么交换a[prev] 和 a[key] ，让key=prev ，此刻key 为分割点。

优化思路：

实际上我们发现当prev 紧跟cur 时，它俩指向的是一个位置的元素，所以这种情况是没必要交换的，所以可以提前判断一下 ++prev!=cur ，如果不满足这个条件，那么直接就不要交换了，反正是同一个位置的值。

接着来写一下代码：

int partion3(int* a, int begin, int end)
{
  int prev = begin;
  int cur = begin + 1;
  int key = begin;
  while (cur <= end)
  {
    // 找到比 key 小的值时，跟 ++prev 位置交换，
    // 小的往前翻，大的往后翻
    // 重复数据不会交换 - 优化后
    if (a[cur] < a[key] && ++prev != cur)
    //a[cur] < a[key] 小才执行++prev，否则不++
      Swap(&a[cur], &a[prev]);
    // 重复数据会交换 - 优化前
    /*if (a[cur] < a[key])
      Swap(&a[++prev], &a[cur]);*/
    cur++;
    // cur 必定会走一步
  }
  Swap(&a[prev], &a[key]);
  //return prev; // 也可以 key，prev 和 key 是相等的
  key = prev;
  return key;
}

2.3 缺陷分析及优化

缺陷1：有序或接近有序序列时间复杂度过高

其实对于快排来说，它的时间复杂度是不稳定的，比如上方三个版本，在乱序的序列中，效率可能还可以，因为选取的 key 值是随机的。 但是对于有序序列，比如要排正序(逆序)，但是序列是逆序(正序)。如果每次选 key 还是按照之前的选法，那么每次可能就会选中最边上的一个，选中最大或最小的数，假设序列长度为N ，每次选取一个极端值，就会选取 N 次，就会递归 N 层，每一层中的时间复杂度为 O ( N ) ，那么最终时间复杂度为O(N^2) 。且栈会溢出，递归 N 层，建立N个栈帧。

改进方法：

1.随机选K，会优化很多，但若刚好随机到最左边，所以不是很推荐

2.我们能否每次选 key 作为一段区间的中位数 ，让每段区间被二分，那么最终就只会递归 logN 层，每层时间复杂度为 O(N) ，总时间复杂度为O(N×logN) 。就像下图，像一棵二叉树一样。 所以这边就引申出了第一个优化：三数取中

所谓三数取中，就是不取最大，不取最小，在begin , end,(begin+end)/2 中选取一个中间值，尽量让key 可以命中每段区间中点。

代码：

int GetMidNum(int* a, int begin, int end)
{
  int mid = (begin + end) >> 1;//   /2
  if (a[begin] < a[mid])
  {
    if (a[mid] < a[end])
    {
      return mid;
    }
    else if (a[begin] > a[end])
    {
      return begin;
    }
    else
    {
      return end;
    }
  }
  else // a[begin] >= a[mid]
  {
    if (a[mid] > a[end])
    {
      return mid;
    }
    else if (a[end] > a[begin])
    {
      return begin;
    }
    else
    {
      return end;
    }
  }
}

缺陷2：不必要的递归层数太多，空间浪费

假设我们只有 10 个数，那么这种情况采用递归是不是浪费空间，是不是多此一举？

所以当 end−begin+1<10 时，可以采用插入排序优化，这样子就不用开太多层函数栈帧。对于一棵满二叉树，最后一层的节点数占总结点数的 我们就假定快排递归展开后，最后形态为完全二叉树。假设当前有10个节点，那么对于下图中红色箭头标出的点来说就无须递归，因为再细分也就是一个数：

大约可以节省下三层的递归，下三层的节点数占总结点数的 87.5 % ，省去了大部分的递归

所以这边就引申出了 第二个优化：小区间优化

但区间不能太大，不然也没有意义了，建议end−begin+1< 10左右

void QuickSort(int* a, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
  // 小于一定数目使用 直接插入排序
  if ((end - begin + 1) < 10)
  {
        // 数组位置：a + begin  ,  直接写a就始终是前几个数
        // 元素个数：end - beghin + 1
    InsertSort(a + begin, end - begin + 1);
  }
  else
  {
    int key = partion3(a, begin, end);
    // 递归左右区间
    QuickSort(a, begin, key - 1);
    QuickSort(a, key + 1, end);
  }
}

缺陷3：对于相同数据来说，三数取中无效，时间复杂度过高

像 2 2 2 2 2 2 2 2 这个序列来说三数取中是完全无效的，特别数据量一大，不仅容易超时，还容易栈溢出。

这就引申出了第三个优化：三路划分。

之前我们是主要将区间划分为两段，[begin,key−1] 和[key+1,end] 。 左区间值小于key ，右区间值大于key ，可以称为 两路划分 。

现在我们需要进行三路划分，就是将区间分割为左区间小于key ，中间区间等于 key ，右区间大于 key 。

思路：

1.设定一个 cur=begin+1，left = begin, right = end, key = a[left]，将区间分割为左区间小于key ，中间区间等于 key ，右区间大于key 。

2.给定一个循环，循环中如果a[cur]<key ，此刻交换 cur 和left 指向的元素，使 left++ ，cur++ (如果一开始这个条件就满足，则会把 key 逐渐往中间推)

3.如果a[cur]>key ，此刻right 这个位置的值比 key 大，也有可能比 key 小。交换cur 和right 指向元素后，若cur++可能该位置元素就不满足最终区间划分条件，所以这里只能right−−.

4.如果a[cur]==key ，那么只需要 cur++。

5.当cur>right 时，right 后的元素都是大于key 的，区间也都调整好了，这时候循环也就停止了。

实际上这一过程就像把和 key 相等的值往中间推，把比 key小的值往左边推，把比 key 大的值往右边推，最后等于key 的就在中间。

最后分割成的区间就是[begin,left−1],[left,right],[right+1,end]，这时等于 key 的区间不用递归，只需要递归排序左右区间即可。

代码：

// 三路划分 处理重复数据量大的情况，处理完中间区间就是 22222222222
void QuickSortT(int* a, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
    // 三数取中一下
  int mid = GetMidNum(a, begin, end);
  Swap(&a[mid], &a[begin]);
  int left = begin, right = end;
  int cur = begin + 1;
  int key = a[left];
  // 跟 key 相等的值，往后推
  // 比 key 小的甩到左边
  // 比 key 大的甩到右边
  // 和 key 相等的就在中间
  while (cur <= right)
  {
    if (a[cur] < key)
    {
      Swap(&a[cur], &a[left]);
      left++;
      cur++;
    }
    else if (a[cur] > key) // 
    {
      // r 这个位置有可能比 Key 大，也有可能比 key 小
      // 所以 cur 不 ++ 
      // 如果 cur 比 key 大，之后还是得换回去处理
      Swap(&a[cur], &a[right]);
      right--;
    }
    else
    {
      cur++;
    }
  }
  // 区间被划分为 [begin, left - 1] [left, right] [right + 1, end]
  QuickSortT(a, begin, left - 1);
  QuickSortT(a, right + 1, end);
}

2.4 快排递归版本完整代码

这边调用的 partion3 是 前后指针版 的代码：

int GetIndexMid(int* a, int begin, int end)
{
  int mid = (begin + end) >> 1;
  if (a[begin] < a[mid])
  {
    if (a[mid] < a[end])
    {
      return mid;
    }
    else if (a[begin] > a[end])
    {
      return begin;
    }
    else
    {
      return end;
    }
  }
  else // a[begin] >= a[mid]
  {
    if (a[mid] > a[end])
    {
      return mid;
    }
    else if (a[end] > a[begin])
    {
      return begin;
    }
    else
    {
      return end;
    }
  }
}
int partion3(int* a, int begin, int end)
{
    // 三数取中
  int mid = GetIndexMid(a, begin, end);
  Swap(&a[begin], &a[mid]);
  int prev = begin;
  int cur = begin + 1;
  int key = begin;
  while (cur <= end)
  {
    // 找到比 key 小的值时，跟 ++prev 位置交换，
    // 小的往前翻，大的往后翻
    // 重复数据不会交换
    if (a[cur] < a[key] && ++prev != cur)
      Swap(&a[cur], &a[prev]);
    // 重复数据会交换
    /*if (a[cur] < a[key])
      Swap(&a[++prev], &a[cur]);*/
      // cur 必定会走一步
    cur++;
  }
  Swap(&a[prev], &a[key]);
  //return prev;
  key = prev;
  return key;
}
void QuickSort(int* a, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
  // 小于一定数目使用 直接插入排序
  if ((end - begin + 1) < 15)
  {
    InsertSort(a + begin, end - begin + 1);
  }
  else
  {
    int key = partion3(a, begin, end);
    // 递归左右区间
    QuickSort(a, begin, key - 1);
    QuickSort(a, key + 1, end);
  }
}

2.5 快排非递归版本

由于递归版本存在缺陷：

1.效率

2.深度太深，会栈溢出

所以我们要具备一个能力：把递归改成非递归

1.直接该成循环。eg.斐波那契数

2.使用栈辅助改循环

非递归的好处就是不需要多次递归开辟多层函数栈帧，在空间消耗上略有优势。

快排的非递归需要借助数据结构 - 栈 来完成。 快排递归的过程相当于对每一段区间进行处理，那非递归可以用两个变量来模拟各个区间

思路：

1.开始，我们将 begin 和 end 分别入栈。给定一个循环，如果栈不为空就继续循环。

2.由于栈是后进先出，所以先用right 接收end 右区间，再用 left 接收左区间，在接收完之后，将这两个元素分别出栈。

3.得到了区间后，对区间进行单趟排序(可以调用上面的 hoare 等)，用 key 接收分隔点。

4先处理左区间[left,key−1] ，再处理 [key+1,right] 。由于栈先进后出，所以要先入右区间，在入左区间。

5.每次循环只会取出两个值，那么就是一小段区间，在取出左区间后，会先处理左区间，然后不断分割小区间，每次取出两个值一直对栈顶上的两个元素的区间进行处理，这样就模拟了快排的过程。

优化思路：

如果区间内只有 1 个元素，就无需处理了，所以可以加个条件判断一下，举个例子，对于右区间来说， key 是分割点， key+1 则是右区间的起始位置，如果key+1<right ，那么说明区间中不止一个元素，这种情况就入栈处理。类比左边也是一样的道理。

// 快排非递归
void QuickSortNorR(int* a, int begin, int end)
{
  ST st;
  StackInit(&st);
  // 压栈
  StackPush(&st, begin);
  StackPush(&st, end);
  while (!StackEmpty(&st))
  {
    // 后进先出，先出 right
    int right = StackTop(&st);
    StackPop(&st);
    int left = StackTop(&st);
    StackPop(&st);
    //单趟排 
    int key = partion3(a, left , right);
    //[left,key−1] key [key+1,right] 
    // 如果区间内只有1个元素，则无需入栈
    // 如果先取左区间，后取右区间
    // 那么先入右区间再入左区间
    if (key + 1 < right)
    {
      StackPush(&st, key + 1);
      StackPush(&st, right);
    }
    if (left < key - 1)
    {
      StackPush(&st, left);
      StackPush(&st, key - 1);
    }
  }
  StackDestroy(&st);
}

2.6 特性及复杂度

对于快排的时间复杂度，本来是不太稳定的，因为处理有序序列或者序列中元素相同的情况下，可能会造成O(N^2) 的时间复杂度。

但是当我们使用 三数取中 或者 三路划分 后，时间复杂度就相对稳定了。

加上这两个功能之后，如果画出每层的元素情况，就像下图一样，像一棵完全二叉树。

由于每次每一块都是被二分，一共 N 个节点，所以这边大约就是logN 层。

对于递归的版本，需要开 logN 层栈帧；对于非递归的版本，原理和递归类似，也认为处理logN 次。每次单趟递归处理中，时间复杂度为 O(N) 。所以快排的时间复杂度为O(N*logN)

空间复杂度也因为优化的原因，几乎不会出现极端情况，我们认为最佳情况就是像二叉树一样，最多开辟logN 层栈帧

递归版本空间复杂度的计算公式：递归深度×每次递归中额外空间消耗，每次递归消耗空间为O(1) ，一共 logN 层，所以空间复杂度为 O(logN) ，非递归同理

特性：快速排序整体的综合性能和使用场景都是比较好的，故称快速排序。

时间复杂度：O(N*logN) 。快速排序的过程类似于高度为 logN 的二叉树，且每层约有 N

空间复杂度：O(logN) 。

稳定性：不稳定。

3.总结：

今天我们认识并具体学习了交换排序算法中的冒泡排序和快速排序，通过这次的学习，我们也感受到了快速排序的魅力。下一篇博客，我们将继续学习排序算法中的归并排序。希望我的文章和讲解能对大家的学习提供一些帮助。

当然，本文仍有许多不足之处，欢迎各位小伙伴们随时私信交流、批评指正！我们下期见~