数据结构：快速排序（扩展）

前面我们详细讲解了快速排序的基本思想、三种找基准值的方法以及各自的时间复杂度分析。不过，快速排序的实现方式远不止这些，本文作为拓展内容，再为大家补充几种其他常见的实现思路，帮助大家更全面地理解这一经典算法。

三路划分找基准值

当面对有大量跟 keyi 值相同的值时，三路划分的核心思想有点类似 hoare 的左右指针和 lomuto 的前后指针的结合。核心思想是把数组中的数据分为三段【比 keyi 小的值】【跟 keyi 相等的值】【比 keyi 大的值】，所以叫三路划分算法。

思想

同样地我们把序列初始位置定为 left ，末尾位置定为 right ，将 left 位置作为基准值。
再定义一个 cur ，指向 left 的下一个位置。

我们的思路是这样的：
cur 当前指向的值小于基准值，就把 cur 处的值和 left 处的值交换一下位置，cur++，left++；
cur 当前指向的值大于基准值，就把 right 处的值和 cur 处交换一下位置， right – -；
cur 当前指向的值等于基准值， cur ++；
我们来走一遍：
cur 指向 2 ，比基准值小，和 left 处数据交换位置，然后 cur ++ ，left ++。

可以发现基准值位置变了，所以我们一开始要存储一下基准值。目前 cur 比基准值大，和 right 交换一下位置， right – -。
（和 right 交换完为什么不 cur ++呢？我们可以看到， right 处指向的是 8 ，比 cur 处都大，也就是 right 处的数据大小我们不知道，所以交换后 cur 也不能++去下一个位置， left 我们是保证了一定比基准值小的，所以可以++）

cur 处比基准值大，和 right 处数据交换，right – -。

cur 处比基准值大，和 right 处数据交换，right – -。

cur 处比基准值小，和 left 交换数据， cur ++， left ++。

cur 处比基准值大，和 right 处数据交换，right – -。

cur 处比基准值大，和 right 处数据交换，right – -。

cur 处比基准值大，和 right 处数据交换，right – -。

此时 cur ＞ right ，结束循环，将 left 位置返回去，基准值就找到了。## 代码实现
我们先初始化一下 keyi ， cur 。

然后写一个 while 循环，循环条件为 cur ＜ right ，内部实现三个逻辑： cur 比基准值大、比基准值小、等于基准值。

当 cur 处数据小于基准值时，和 left 处交换数据， left++， cur++。
当 cur 处数据大于基准值时，和 right 处交换数据， right – -。
当 cur 处数据等于基准值时， cur++。

循环结束后将 left 处作为基准值位置返回去，基准值找到了。代码就写完了。

我们来简单测试一下：

结果符合预期，代码没什么问题。

时间复杂度

可以看出来三路划分代码时间复杂度是一个很标准的O（n），递归次数最好是 logn ，最坏是 n。
因此三路划分快速排序的时间复杂度平均为O（nlogn），最坏为O（n²）。

快速排序之自省排序

Introsort 是 introspective sort 的缩写，他的名字其实表达了他的实现思路，他的思路就是进行自我侦测和反省，快排递归深度太深，那就说明在这种数据序列下，选 keyi 出现了问题，性能在快速退化，那么就不要再进行快排分割递归了，改换为堆排序进行排序。# 非递归版本快速排序
非递归版本的快速排序如何实现呢？

因为 lomuto 前后指针的代码比较简单，所以这里我们选用它来查找基准值，关键在于，如何拿到左右序列的区间然后一直往下分地找基准值。## 思想

比如我们先找基准值分出左右序列。

这里左序列区间就是 [0,2] ，右序列区间就是 [4,8] 。先找哪边序列的基准值都可以，这里我们选择先找左序列的，找到了要怎么往下继续分左右序列，这个问题如何解决？
我们需要借助一种数据结构 —— 栈来存储序列的左右区间。
我们先把序列的区间入栈，先入左区间，再入右区间。

这样栈就不为空了，我们先找基准值，把序列的区间取出来，第一次取到的栈顶是右区间，第二次是左区间。

分出来左右序列，我们先把右序列区间入栈，再入左序列的区间，这样第一次取出来的就是左序列的区间，相当于先给左序列找基准值。

我们取两次栈顶，第一次取到的是右区间，第二次是左区间，然后找基准值。

这时左序列区间为 [0,-1] ，说明左序列不存在，不入栈了，右序列区间为 [1,2]，入栈。

我们再取两次栈顶元素，找该区间的基准值。

这时左序列区间为 [1,0]，说明左序列不存在，不入栈，右序列区间为 [2,2]，只有一个数据，不用找基准值，也不用入栈。

继续取两个栈顶元素，在该区间找基准值。

分出的左右序列区间都存在，入栈。

再取两次栈顶元素，在该区间内找基准值。

左右序列不存在，不用入栈，继续取两次栈顶元素，在该区间内找基准值。

左右序列不存在，不用入栈，此时栈为空，快速排序结束。
继续取两个栈顶元素，在该区间找基准值。

分出的左右序列区间都存在，入栈。

再取两次栈顶元素，在该区间内找基准值。

左右序列不存在，不用入栈，继续取两次栈顶元素，在该区间内找基准值。

左右序列不存在，不用入栈，此时栈为空，快速排序结束。

总结来说就是，循环取两次栈顶元素，在该区间内找基准值，分出的左右序列存在则入栈，然后再循环取栈顶元素，继续找，直到栈为空为止。

代码实现

我们把实现栈的那些东西拿过来，这里具体来实现非递归版本快速排序代码。

我们先初始化一个栈，然后把原序列区间入栈，保证栈不为空。

当栈不为空时找基准值就没有结束，所以循环条件为 !StackEmpty(&st)。

我们先取两次栈顶元素，然后用 lomuto 前后指针办法找基准值。

找到基准值位置后，左序列区间就是 [begin,keyi-1] ，右序列区间是 [keyi+1,end]。先入右序列再入左序列的区间，序列存在则入。

然后一次循环就结束了，接下来会进入下一次循环，非递归版本快速排序代码就完成了。

我们来测试一下：

结果符合预期，说明代码没有什么问题。## 时间复杂度
时间复杂度为O(nlogn)，最坏情况下也为O（n²）。依然是找基准值分左右序列这步主要影响时间效率。