快速排序（三）——hoare法

一.前言

本文给大家带来的是快速排序，快速排序是一种很强大的排序方法，相信大家在学习完后一定会有所收获。

码字不易，希望大家多多支持我呀！（三连＋关注，你是我滴神！）

二.快速排序

快速排序是Hoare与1962年提出的一种二叉树结构的交换排序方法，其基本思想为：任取待排序元素排序中的某元素作为基准值，按照该排序码将待排序集合分割成两子序列，左子序列中所有元素均小于基准值，右子序列中所有元素均大于基准值，然后最左右子序列重复该过程，直到所有元素都排列在相应位置上为止。

上述为快速排序递归实现的主框架，发现于二叉树前序遍历规则非常像，同学们在写递归框架时可想想二叉树前序遍历规则即可快速写出来，后序只需分析如何按照基准值来对区间中数据进行划分的方式即可。

今天我们来学习的是第一种版本：

hoare排法

下面是动态图例：

开始解析：

简单点讲就是我们找到一个数成为key，然后从右边出发找到比key小的数（如5）

然后左边再出发找比key大的数（如7）

然后让这两个值交换，意义是把比key小的值尽量放左边，比key大的值尽量放右边

交换完之后呢，右边再继续找小（如4）

左边也继续找大（如9）

然后两者再进行交换

再继续找小（如3）

再继续找大，但没找到反而相遇了，那就停下

然后最让key与相遇的位置交换

最后我们发现比key小的都在其左边，比key大的都在右边了。

右边找比key小的值找到后停下换左边找比key大的值然后也停下最后二者交换，直到key到达最终位置。

所以单趟的意义就是：使key到达正确（排好序要放的位置）

老规矩，我们先来分析一下单趟排序代码：

那不妨想一想如果key左边5个数有序，右边4个数也有序，那么就完成排序的目的了。

而这又与我们之前学习的二叉树遍历很像，根，左子树，右子树遍历，再对左子树进行分割根，左子树，右子树遍历——前序遍历。

当我们把这个想象成二叉树分治遍历，那么就是排序全部完成的时候了。

我们可以快速来一遍单趟，设3为key，然后右边找小（2）,左边找大（没找到相遇了），与key交换。

3不用动了，再分割出左边选一个key出来。

继续右边找小（找不到）交换。

我们把它看成二叉树，当排好最后一组时开始往回递归，遇到key为2的一组时再往右递进，发现是空子树回归，然后继续往上到key为3的一组，对其右子树（5 4 ）继续递进。

至此，左边排序已经排好了。

这样对右子树（6右边的排序）持续下去结束后，整个数组的排序完成。

接下来是代码部分：

int PartSort(int* a, int left, int right)
{
  int key = a[left];
  while (left < right)
  {
    //找小
    while (a[right] > key)
    {
      right--;
    }
    //找大
    while (a[left] < key)
    {
      left++;
    }
    Swap(&a[right], &a[left]);
  }
  Swap(key, &a[left]);
  return left;
}

我们定好key下标，首先当left与right相遇的时候（left==right)才会让key交换，所以我们第一层循环用的是left<right。

然后是找大和找小我们第二层循环就正常比较大小++和--就行了。

我们作好大体框架再从细节处出发(找bug）：

当我们修改数组中的2个数字再次排序时。

我们会发现left与right都会在6这个位置停下，这样造成的结果就是死循环！

所以我们需要修改条件

而在我们处理好上面这个问题后又会出现新问题：数组越界

可以发现如果是如图中数组，那么right就会不断--移出数组外造成越界问题。

所以需要添加条件（让right--时遇到left就停下，避免越界），left同理。

int PartSort(int* a, int left, int right)
{
  int key = a[left];
  while (left < right)
  {
    //找小
    while (left<right && a[right] >= key)
    {
      right--;
    }
    //找大
    while (left < right && a[left] <= key)
    {
      left++;
    }
    Swap(&a[right], &a[left]);
  }
  Swap(&key, &a[left]);
  return left;
}

还有一个问题：当key发生交换的时候只是数值发生了交换，但key还是在原来的位置，所以我们需要把它移动到交换后的位置。

这样就可以

int PartSort(int* a, int left, int right)
{
  int keyi = left;
  while (left < right)
  {
    //找小
    while (left<right && a[right] >= a[keyi])
    {
      right--;
    }
    //找大
    while (left < right && a[left] <= a[keyi])
    {
      left++;
    }
    Swap(&a[right], &a[left]);
  }
  Swap(&a[keyi], &a[left]);
  return left;
}

接下来就是处理分治问题：

void QuickSort(int* a, int begin, int end)
{
  int keyi = PartSort(a, begin, end);
  //[begin,keyi-1]key[keyi+1,end]
  QuickSort(a, begin, keyi - 1);
  QuickSort(a, keyi + 1, end);
}

然后我们需要制定一个结束的条件：

• 只有一个数的时候（left==right）结束
• 没有数的时候（left>right)

void QuickSort(int* a, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
  int keyi = PartSort(a, begin, end);
  //[begin,keyi-1]key[keyi+1,end]
  QuickSort(a, begin, keyi - 1);
  QuickSort(a, keyi + 1, end);
}

下面这是递归展开图：

我们来用100万个随机数来测试一下快排的性能

可以看到快排的效率是名不虚传的~

在我们写完快排后再来回顾几个问题：

为什么相遇的位置一定比key小呢？

如果相遇的位置比key大，那交换肯定是会出问题的。

我们重新按原位置开始走，当快要相遇时，在R先走的情况下 ，能让R停下的是比key小的3。这样是让L走然后与R相遇。验证了R先走，相遇值比key小。

如果一开始是L先走，走到同样情景时，因为是L先走它会去找比key大的数，就这样找到了9，也与R相遇，但这样最后交换是错误的，相遇的位置比key大。

我们再换一种情况，把3换成10：

我们会发现如果是R先走，那么它会找小，最后越过10找到了4并与L相遇.因为L的位置一定是比key小的数字，毕竟它下标对应的数字是由R(负责找比key小的数字）找到并交换过来的。验证了R先走，相遇值比key小。

那如果是L先走呢？在10停下后等R相遇然后交换，最后发现交换是错误的，因为出现了左边（10）比key(6)大的情况，相遇值比key大。

最后是一种极端情况：在几乎是升序的数组里R从右边先走直到和L相遇，相遇的位置没有比key小。交换后对其右边的一组数值再进行分治划分，

经过这几种情况分析我们可以发现，如果是L先走然后相遇值都是比key大的，并且交换都会出现错误。而在R先走然后相遇值都是比key小的，并且交换不会出现错误。

相信大家应该发现了，key在左边的时候我们就让右边先走，key在右边的时候我们让左边先走。

因为当key在左边的时候我们要确保最后的相遇值是比key小的，这样交换过来才能符合升序的规则，所以我们让R先走确保它找到的值一定是小的。同理key在右边时我们要确保交换过来的相遇值要比key大，这样才能符合升序规则，而让L先走就一定能确保它找到的是比key大的值。

最终我们需要学会根据key的位置不同，升序降序的规则不同合理作出相应的变化~

下面我们来分析快排的第二个问题：快排的效率分析

假设我们每一次选出的key都是中位数就会呈现出这种情况

我们可以看到每一层的单趟排序其实都可以看作是N次执行（在数很多的情况下），因为每一层合计起来也差不多是N这个量级。

而它的高度是logN,这样它的总的时间复杂度度就是O(N*logN)

但这只是比较理想的情况下，如果是在接近有序的情况下，它的高度就会变成N，这样时间复杂度的就会是O（N^2)

为了避免快排在有序的情况下效率受到干扰，我们设置了一个叫三数取中的方法。（不是位置取中，而是数值取中）

改变选key的策略，不再是固定选左边的值作key，但如果是中间的值作key又是先走左边还是右边呢，这样也会影响到单趟排序。其实我们可以一直选左边的值作key，就算你选到的key在中间把它换到左边就行了。

这样无论是有序还是无序最终key的交换落点都能尽量落到与下图差不多的位置，避免了有序时算法效率的损耗。

最终代码：

int GetMidi(int* a, int left, int right)
{
  int mid = (left + right) / 2;
  // left mid right
  if (a[left] < a[mid])
  {
    if (a[mid] < a[right])
    {
      return mid;
    }
    else if (a[left] > a[right])  // mid是最大值
    {
      return left;
    }
    else
    {
      return right;
    }
  }
  else // a[left] > a[mid]
  {
    if (a[mid] > a[right])
    {
      return mid;
    }
    else if (a[left] < a[right]) // mid是最小
    {
      return left;
    }
    else
    {
      return right;
    }
  }
}
int PartSort(int* a, int left, int right)
{
  int midi = GetMidi(a,left,right);
  Swap(&a[midi], &a[left]);
  int keyi = left;
  while (left < right)
  {
    //找小
    while (left<right && a[right] >= a[keyi])
    {
      right--;
    }
    //找大
    while (left < right && a[left] <= a[keyi])
    {
      left++;
    }
    Swap(&a[right], &a[left]);
  }
  Swap(&a[keyi], &a[left]);
  return left;
}
void QuickSort(int* a, int begin, int end)
{
  if (begin >= end)
  {
    return;
  }
  int keyi = PartSort(a, begin, end);
  //[begin,keyi-1]key[keyi+1,end]
  QuickSort(a, begin, keyi - 1);
  QuickSort(a, keyi + 1, end);
}

三.结语

本次我们介绍了hoare的快排法，相信大家都发现了有很多的坑点需要我们注意，不过放心，下一篇文章我会介绍在原基础上优化更加的其他快排法~最后感谢大家的观看，友友们能够学习到新的知识是额滴荣幸，期待我们下次相见~