前端学数据结构与算法（十）：深入理解快速排序
前言 上一章我们已经实现了快速排序，在数据理想化的情况下，上一章的快排性能确实也不错，但如果数据比较极端的，快排的O(nlogn)就不太稳定了，本章将介绍几种快排应对极端数据下优化方案；以及介绍partition操作延伸出来的快速选择算法在解决top K问题时高效。 优化分区点的选择 上一章我们直接选择了数组的范围内的第一个元素作为分区点，当数据有序度很低时，这样选择确实也没问题。但是如果本身就是一个有序数组，这个时候就会出问题： 因为partition的操作是以分区点为中心，将数组一分为二。而此时数组是有序的，也就是说每次选择的这个分区点无法将数组一分为二，会导致快排最终的复杂度退化为O(n²)。所以此时要改变选择分区点的规则。 三数取中 不仅是从头部，无论是从数组哪个位置，只要是单单选择一个位置，都有可能出现退化的情况。所以我们可以多选几个位置从里面挑一个出来。如从范围数组中的头、中间、尾选择三个元素，比较它们的大小，选择中间大小的值作为分区点。这样就能避免遇到有序数组时的退化情况，代码如下： const quickSort = arr => { const _quickSort = (arr, l, r) => { if (l >= r) { // 递归终止条件 return } const p = _partition(arr, l, r) // 返回分区点所在下标 _quickSort(arr, l, p - 1) // 递归进行左半部分 _quickSort(arr, p + 1, r) // 递归进行右半部分 } _quickSort(arr, 0, arr.length - 1) } function _partition(arr, l, r) { // 三数取中分区点 const mid = l + (r - l) / 2 | 0 // 中间位置 const t1 = arr[l] > arr[mid] ? l : mid const t2 = arr[t1] > arr[r] ? r : t1 swap(arr, l, t2) // 让最左侧的l和中间大小的值交换位置 const v = arr[l] // 让中间值作为分区点 let j = l for (let i = l + 1; i <= r; i++) { // 从l + 1，刨去分区点的位置 if (v > arr[i]) { // 当分区点大于当前节点时 swap(arr, j + 1, i) // 让大区间的开头与当前节点交换 j++ // 小区分范围增加 } } swap(arr, j, l) // 最后让分区点回到其所在位置 return j // 返回其下标，进行接下来的分区操作 } function swap (arr, i, j) { [arr[i], arr[j]] = [arr[j], arr[i]] } 随机选择 从被需要排序数组的区间中随机选择一个位置作为分区点，虽说不能保证每次都选到合适的值作为分区点，但从概率来说，每一次都选到数组里最大或最小的值，概率几乎为0，理想中能保持O(nlogn)的复杂度，这个方法也经常被采用。代码如下： const quickSort = arr => { const _quickSort = (arr, l, r) => { if (l >= r) { // 递归终止条件 return } const p = _partition(arr, l, r) // 返回分区点所在下标 _quickSort(arr, l, p - 1) // 递归进行左半部分 _quickSort(arr, p + 1, r) // 递归进行右半部分 } _quickSort(arr, 0, arr.length - 1) } function _partition(arr, l, r) { // 随机选择分区点 const rdmIndex = Math.random() * (r - l + 1) + l | 0; swap(arr, l, rdmIndex) // 让最左侧的l与随机下标交换位置 const v = arr[l] // 让随机值作为分区点 ... } 应对重复数据过多的三路快排 上面我们解决了分区点选择的问题，但此时又有一个新的问题。假如一个数组里面有100万条数据，但它的取值范围都是0 ~ 10，此时再采用之前的partition算法就不行了。因为重复数据比较多，而上面partition里没有对值相等时的情况处理，会造成相等的数据全部堆积在分区数组其中的一边，又回到上一个问题，会导致分区极度不平衡。 此时我们可以使用三路快排，它会对相等的数据做单独的处理，不在仅仅是一分为二，而是一分为三，将相等的数据单独作为一个区间。而且再进行递归时，可以将相等的区间刨除在外，只对小区间或大区间进行partition操作，减少操作次数。图解示例如下： 还是有两个边界下标left/right，游走下标更换为lt/i/gt，lt表示为小区间的最后一位，i表示为当前访问到的元素，也可以理解为等于区间的最后一位，gt表示大区间的第一位。这次的partition操作将比较分为三种情况： 小于分区点 我们需要将lt + 1与i进行交换，并将lt和i依次进行后移。因为lt表示为小区间的最后一位，所以lt + 1就表示等于区间的第一个元素，而此时i又小于区间值，所以交换后lt依然是小区间的最后一位，而i继续遍历下一个元素。 大于分区点 我们需要将gt - 1与i进行交换，因为gt表示的是当前大区间的第一位，而gt - 1则表示最红等于区间的最后一位，交换位置之后，大区间的范围也就增加了。此时仅仅gt前移一位即可，i不需要移动，因为交换过去的值还不确定它的大小，正好作为当前元素即可。 等于分区点 那么i + 1即可，增加等于区间的范围及遍历下一个元素，lt/gt坐标都不需要移动。最终i与gt碰上之后结束遍历过程。 代码如下： const quickSort3Ways = arr => { const _quickSort3Ways = (arr, l, r) => { if (l >= r) { return } const rdmIndex = Math.random() * (r - l + 1) + l | 0 // 选择随机分区点 [arr[l], arr[rdmIndex]] = [arr[rdmIndex], arr[l]] const v = arr[l] let lt = l let gt = r + 1 let i = l + 1 while (i < gt) { if (arr[i] < v) { // 小于区间值 [arr[i], arr[lt + 1]] = [arr[lt + 1], arr[i]] lt++ i++ } else if (arr[i] > v) { // 大于区间值 [arr[i], arr[gt - 1]] = [arr[gt - 1], arr[i]] gt-- } else { // 等于区间值 i++ } } [arr[l], arr[lt]] = [arr[lt], arr[l]] // 交换分区点与小区间的最后一位，维持三个区间 _quickSort3Ways(arr, l, lt - 1) // [l ... lt-1]表示的就是小区间 _quickSort3Ways(arr, gt, r) // [gt ... r]表示的就是大区间 // 而直接可以舍弃等于区间，提高效率 } _quickSort3Ways(arr, 0, arr.length - 1) } 改用遍历的方式，不用担心调用栈溢出的情况，且三分之后，相等区间的范围在每次遍历时都可以直接忽略掉，因为它们已经在最终排好序的位置。 使用插入排序代替小范围排序 O(nlogn)的排序算法的确是比O(n²)快很多，但这描述的是随着数据规模n的增长而增长的趋势，这里忽略了常数以及低阶的情况，而当n小到一定常数时使用插入快排代替就是一种合理的选择，因为范围小则它有序度高的几率就大，插入排序在应对近似有序时的效率又奇高。可以这么理解，快排虽然快，但它的启动会慢一些。 const quickSort = arr => { const _quickSort = (arr, l, r) => { if (r - l < 10) { // 终止条件替换为插入排序 insertSort(arr, l, r) return } const p = _partition(arr, l, r) // 返回分区点所在下标 _quickSort(arr, l, p - 1) // 递归进行左半部分 _quickSort(arr, p + 1, r) // 递归进行右半部分 } _quickSort(arr, 0, arr.length - 1) ... } 当要待排序的数组小到一定程度时，我们改为插入排序，同时这里的插入排序也需要改一下，给它限定排序的范围： const insertSort = (arr, l, r) => { for (let i = l + 1; i <= r; i++) { let e = arr[i] let j; for (j = i; j > l && arr[j - 1] > e; j--) { arr[j] = arr[j - 1] } arr[j] = e } } 比堆更有效率的解决top-K问题 这是之前第七章介绍堆的一个力扣题目，当时使用的堆解决，堆能在O(nlogk)的时间复杂度里解出，这已经是合格的解法了，不过在此借鉴快排的partition思想后，能交出O(n)的满分答案。先来回顾下题目： 215-数组中的第K个最大元素 ↓ 在未排序的数组中找到第 k 个最大的元素。 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。 示例： 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5 我们知道partition操作会把分区点放在合适的位置，最后返回它所在的下标，而这个下标恰恰就是当数组完全排好序后，它正好所在的位置，所以我们只需要找到下标正好等于K的元素即可。 这里又会有两种情况，返回的下标大于K或者小于K，因为partition操作已经对数组进行了分区，所以只需要将返回的下标与K进行比较即可，如果大于就去大区间查找，反之亦然。每次查找平均可以舍弃一半的查找范围，所以这个算法最差也是O(n)的时间复杂度。代码如下： var findKthLargest = function (nums, k) { if (nums.length === 0 || k > nums.length || k < 0) { return -1; } const _partition = (nums, l, r) => { // 返回对应下标 const rdmIndex = (Math.random() * (r - l + 1) + l) | 0; [nums[rdmIndex], nums[l]] = [nums[l], nums[rdmIndex]]; const v = nums[l]; let j = l; for (let i = l + 1; i <= r; i++) { if (nums[i] > v) { // 采用降序，正好对应第k大 [nums[i], nums[j + 1]] = [nums[j + 1], nums[i]]; j++; } } [nums[l], nums[j]] = [nums[j], nums[l]]; return j; }; let l = 0; let r = nums.length - 1; while (true) { const p = _partition(nums, l, r); if (p + 1 === k) { // 下标需要加1, 0表示第1大 return nums[p]; } else if (p < k) { // 缩小partition的范围 l = p + 1; } else { r = p - 1; } } }; 严格意义上来说，partition的思想确实在解决这个题目时是最快的解法，但其实它和用堆解法也是各有优劣。 当这个数组是动态随时会有新数据加入其中时，当前解法每次又需要O(n)时间去查找。而堆应对这种场景就有优势了，面对动态的数组集合，每次只需要重新维护堆结构即可，在O(logn)复杂度即可返回结果。 最后 本章我们介绍了关于快排在面对极端数据时的优化以及它延伸出来的快速选择算法，还有在面对高频面试题Top-K问题时与堆处理的优劣(还有尾递归的优化，貌似浏览器不支持，就不列出了)。完全理解快排也算是打通了算法的任督二脉，为更难理解的算法打好基础。作为排序里面的明星算法，快排值得一整个章节。
