上一节我们学习的「快速排序」是一个基础版本的快速排序，我们知道了 partition 的意义：选择一个元素作为切分元素（pivot）
经过一次 partition 以后，这个元素就能挪到排序以后它最终应该在的位置，并且它前面的所有元素都小于等于 pivot，它后面的所有元素都大于等于 pivot，接着我们只需要依次对 pivot 前面的所有元素和 pivot后面的所有元素依次执行同样的逻辑，每次都排定一个元素。
我们还指出了选择标定元素的时候需要随机选择，否则在面对极端测试用例（有序数组或者倒序数组）的时候，递归树会发生倾斜，导致复杂度退化成平方级别。解决的办法是「随机选择切分元素」。
随机选择切分元素有一种情况是无效的，那就是输入数组中有大量重复元素的数据：交换过来的元素还是和 pivot 相等的元素。这个时候我们的策略是：
把和 pivot 相等的元素 平均分到数组的两边
使得递归树平衡，这就有了如下的指针对撞的快速排序
指针对撞的快速排序
以下是两种可行的 partition 过程循环不变量的设置，不管是哪一种，和切分元素相等的元素都全部被划分到了一侧，都会使得递归树失衡，即递归树的深度增加。
那么，有没有办法，让与切分元素相等的元素分散到数组的两侧呢？事实上也不太难，我们这个时候设置两个变量，往中间靠拢，这两个变量分别用 le 和 ge 表示。
循环不变量：在循环的过程中，总有 [left + 1, le) <= pivot 并且 (ge, right] >= pivot 成立；
le的初值是left + 1，ge的初值是right + 1，这样上面的两个区间是空区间；- 我们采用两边夹的方式：
le遇到严格小于pivot的元素的时候自增，直到遇到一个元素大于等于pivot的时候停下；ge遇到严格大于pivot的元素的时候自减，直到遇到一个元素小于等于pivot的时候停下；
此时 le 来到了第 1 个大于等于 pivot 的位置； ge 来到了第 1 个小于等于 pivot 的位置，此时把它们交换，交换以后，它们各自再向中间走一步，重复这样的过程直到它们相遇为止。
请注意：等于 **pivot** 的元素通过交换，换到对面去，而不是直接吸收进来。通过这种方式，实现了等于 **pivot** 的元素平均分到数组两边的效果，从而也保持了循环不变量。
什么时候停下呢？**le > ge** 的时候。最后需要特别注意：交换 left 与 ge 位置上的元素，因为此时 le 已经在 ge 的右边，循环不变量小于等于 pivot 的这个区间是不包括 le 的，因此，le 所指向的元素很可能是大于 pivot，而 ge 来到了 le 的左边。根据循环不变量，它所指向的元素一定是小于等于 pivot 的，因此我们交换 left 与 ge 位置上的元素，我们排定的元素是 ge 所对应的元素，应该把 ge 返回回去。
这种设置两个变量，一个从左往右遍历，一个从右往左遍历的技巧叫做「双指针」（two pointer）或者「指针对撞」。
快速排序的代码框架如下：
- 构建分界点
- 循环
- 随机基准值
arr[Math.floor(Math.random() * (right - left + 1)) + left]
- 基准值左边找比它大的
- 基准值右边找比它小的
- 下标左小右大交换
- 有重复就跳过
- 分界点左边区域继续构建分解点
- 分界点右边区域继续构建分界点 ```javascript // 「力扣」第 912 题：排序数组
const sortArray = function sortArray(nums) { if (nums.length < 2) return nums; // 记得return return quickSort(nums, 0, nums.length - 1); }
const quickSort = function quickSort(nums, left, right) {
if (left >= right) {
return;
}
/** 前序遍历位置 **/
// 通过交换元素构建分界点 p
let p = partition(nums, left, right);
/**递归**/
// 分界点 p 已经排好了
quickSort(nums, left, p - 1);
quickSort(nums, p + 1, right);
return nums;
}
const partition = function partition(nums, left, right) { const randomInt = Math.floor(Math.random() * (right - left + 1)); const pivot = nums[left + randomInt]; let l = left; let r = right; while (l < r) { // 循环，直到在左边区域找到比pivot大的元素 while ([l] < pivot) { l++; } // 循环，直到在右边区域找到比pivot 小的元素 while (nums[r] > pivot) { r—; } // 两个循环出来的时候， 刚好一个大一个小 // 交换就完事了 if (l < r) { [nums[l], nums[r]] = [nums[r], nums[l]]; } // 当数组中存在重复数据时，即都为datum，但位置不同 // 继续递增i，防止死循环 if (nums[l] == nums[r] && l != r) { l++ } } return l; // i 和 j 已经一样了 } ```
练习
- 自行编写测试用例，完成下面的实验：在输入数据有大量重复元素的时候，这一节介绍的快速排序能起到优化的效果；
- 这一节我们没有相关的练习，大家把这一版 partition 写进快速排序的实现里，注意调试，通过「力扣」第 912 题即可。
若有收获，就点个赞吧
0 人点赞
