前面我们讲了交换排序中的冒泡排序接下来让我们一起进入快速排序的学习当中。快速排序快速排序是 Hoare 于 1962 年提出的一种基于二叉树结构的交换排序方法其基本思想为任取待排序元素序列中的某元素作为基准值按照该排序码将待排序集合分割成两个子序列左子序列中所有元素均小于基准值右子序列中所有元素均大于基准值然后对左右子序列重复该过程直到所有元素都排列在相应位置上为止。我们随机取一个数作为基准值。然后将比基准值小的值放到左边的序列中将比基准值大的值放到右边的序列中。然后从左右序列中再找基准值继续划分左右序列直到划分完成为止。从图中我们可以很直观地看出左右序列的划分和二叉树结构很像因此我们可以通过递归分出左右序列。问题就在于基准值如何找关于找基准值我们有好几种方法我们将找基准值封装为一个函数用 keyi 来接收基准值。比如我们上面找到的基准值位置是下标 4。然后我们递归去找它左右序列的基准值就需要把左右序列的区间传过去。因此形参要改一下改为 int* arr、int left、int right。left 是左区间right 是右区间调用该函数递归去找左右区间的基准值。因为 keyi 在下标为 4 的位置一开始传过来的 left 是数组开头也就是下标为 0 的位置right 是数组末尾位置 n - 1。所以左序列区间应该是 [left, keyi-1]右序列区间应该是 [keyi1, right]。我们就可以递归去找左右序列的基准值了。需要注意的是当我们的左右序列划分到只有一个数据或没有数据比如以下这种情况。这时基准值 keyi 位置是 1它的左序列区间为 [0,0]左右区间相等也就是 left right 的情况。只有一个数据时这个数据肯定就是基准值了左右序列也不存在所以在 left right 时不用再去递归找基准值了。我们再来看右序列右序列的区间是 [2,1]也就是 right left 的情况这种情况下右序列都不存在了。综上所述当 left right 时左右序列不存在或者说只剩一个数据就不用再去找基准值了。快速排序的代码大致就写完了接下来我们介绍几种找基准值的方法。Hoare左右指针Hoare左右指针的基本思想是这样的我们定义三个变量 keyi 是基准值 left 是左区间 right 是右区间我们一般把 left 位置作为基准值然后 left指向下一个位置。可以看出left 和 right 需要传参过来指向数组的指针也是所以找基准值的函数参数如下int Partition(int* arr,int left,int right)思路Hoare左右指针具体找基准值的思路是这样的right 从右往左找找到比基准值小的数据。 left 从左往右找找比基准值大的数据。找到后将 left 和 right 指向的数据进行交换也就是把比基准值小的数据放到了左边比基准值大的数据放在了右边。然后按规则继续找。找到后继续交换。然后 right 继续从右往左找比基准值小的数据right-- 找到了 3然后 left 从左往右找找到了 5但此时 right left。这时 left 和 right 就停止查找交换 keyi 和 right 中的数据。此时基准值存放在 right 位置把 right 返回去基准值就找到了。这就是Hoare左右指针找基准值的办法。代码实现我们先定义好 keyi 一般取 left 位置为基准值然后 left 指向下一个位置。我们让 right 先从右往左找比基准值小的数据然后 left 从左往右找比基准值大的数据都找到后交换数据。这个过程循环往复直到 left right 为止。因为 right 和 left 在查找的过程中也有可能越界所以要加上 left ≤ right 这个限制条件。当 left right 的时候也要将这个位置的值和基准值作比较如果进入循环条件写成 left right当 left right 的时候就不会进入循环会把这次与基准值比较漏掉直接交换 right 和 keyi 的值导致错误这里 right 和 left 找到和基准值相等的数据要进行交换原因一会儿再说。找到后交换 left 和 right 的值同样也要保证 left ≤ right。交换完 left 和 right 后直接移一个位置是为了防止 left 和 right 都指向和基准值相同的值从而变成死循环一直交换。整体结束后我们让 right 和 keyi 处的数据进行交换返回 right 基准值的位置就找到了。我们简单测试一下与预期结果符合说明代码没什么问题。为什么和基准值相等的时候也要进行交换我们来看以下数组我们用Hoare版本的找基准值来排序一下该数组假设基准值相同我们也不进行交换首先是 right 指针从右往左遍历去获取比基准值小的数我们会发现 right 会一直 – 来到 keyi 的位置此时 left right跳出循环将 keyi 和 right 的值进行交换返回 right 的位置。这时基准值把原数组分为了左右序列左序列不存在分出右序列这时又开始找基准值right 从右往左遍历找比基准值小的数据发现找不到又来到了 keyi 的位置此时 left right跳出循环交换 keyi 和 right 处的数据将 right 作为基准值下标返回来。这时又分出左右序列左序列不存在分出右序列我们会发现如果基准值相同的时候我们不进行交换每次 right 都会走到 keyi 的位置然后在此分出右序列。对于递归树我们最理想的情况下是每次基准值位置都在数组偏中间的位置这样我们递归树结构就类似于二叉树递归次数是logn。而在这种情况下每次都只减少了一个数据比如说一开始数据个数为 n 下次递归分出的右序列数据为 n - 1 一直往下递归递归次数来到了最坏的 n 次在时间效率上就是大打折扣因此遇到基准值相同的情况我们也要交换避免这种情况的发生。时间复杂度对于代码来说虽然是嵌套了两层while循环但实际上外层循环为有限次因为主要是内部循环中 right 和 left 进行移动外层循环实际上是判断 left ≤ right 是否成立这两个指针必定会在有限步中相遇所以整体时间复杂度为On。对于递归次数理想状态下递归树是一个二叉树结构递归次数来到了 logn 但对于已有序数组递归次数会来到最坏的 n 次和上个问题类似。所以最好情况下Hoare版本的快排时间复杂度为 Onlogn最坏情况下为 On2。挖坑法创建左右指针。首先从右向左找出比基准小的数据找到后立即放入左边坑中当前位置变为新的“坑”然后从左向右找出比基准大的数据找到后立即放入右边坑中当前位置变为新的“坑”结束循环后将最开始存储的分界值放入当前的“坑”中返回当前“坑”下标即分界值下标。按图来说是这样的我们取 left 位置为 hole 坑 left。right 从右往左找比基准值小的数据找到后将 right 处的值放到 hole 中然后 right 变为新的 hole。然后 left 从左往右找比基准值大的数据找到后将 left 处的数据放到 hole 中 left 位置变为新的 hole 。然后 right 继续从右往左找比基准值小的数据找到后将 right 处的数据放入 hole 中right 处成为新的 hole。然后 left 从左往右找比基准值大的数据放入 hole 中 left 处成为新的 hole。right 再从右往左找比基准值小的数据。此时发现 left right 则查找结束将基准值放入 hole 中然后返回来 hole 的位置基准值就找到了。根据思想我们可以看出来需要一个变量来存储基准值因为值会有覆盖问题。根据代码我们可以看出来当 right 或 left 处的数据和基准值相等时不交换因为如果交换的话条件就是 arr[right] tmp这样因为和基准值相等所以 right 指针就不会往左走一直进行交换从而变成死循环。挖坑法用的很少了解一下即可。lomuto前后指针思路创建前后指针将后面比基准值小的值放在前面。同样地我们将 left这里下标为0处作为 基准值 keyi 然后创建一个前指针 prev 指向 left 位置后指针 cur 指向 prev 的下一个位置。具体思路是这样的 cur 去找比基准值小的数据找到后和 prev 的位置去交换直到 cur 遍历完整个序列为止。cur 现在指向的是2比基准值小和 prev 位置交换但此时 cur prev 相当于自己跟自己交换所以我们选择不交换。cur 继续去找比基准值小的数据找到后和 prev 位置交换。然后 cur 继续往下走找到后继续和 prev 位置交换。然后 cur 最后把序列遍历完了。这时我们将 keyi 和 prev 位置处的数据进行数据交换把 prev 位置返回来基准值就找到了。这就是lomuto前后指针找基准值的办法。代码实现我们先初始化创建变量。然后 cur 遍历序列去找比基准值小的数据找到了和 prev 交换数据。跳出循环后交换 prev 和 keyi 处的数据把 prev 返回来。这个代码就写好了实现也是很简单。我们来简单测试一下。结果符合预期代码没什么问题。注对于 cur 遇到和基准值相同的值要不要交换呢其实交不交换都一样如果原序列数据都相同我们 cur 和基准值相同要交换的话递归就会从最右边开始分递归 n 次反之就是从最左边开始分也是递归 n 次无法解决时间效率上的问题所以交不交换都一样。时间复杂度lomuto前后指针的方法很明显就一个循环所以时间复杂度为On至于递归次数和Hoare版本、挖坑法都表现出了一样的缺陷最好情况下是 logn 最坏情况下是n次。因此lomuto版本的时间复杂度最好是Onlogn最坏是On2。