专栏首页数据结构与算法(JavaScript)前端学数据结构与算法(十):深入理解快速排序
原创

前端学数据结构与算法(十):深入理解快速排序

前言

上一章我们已经实现了快速排序,在数据理想化的情况下,上一章的快排性能确实也不错,但如果数据比较极端的,快排的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/gtlt表示为小区间的最后一位,i表示为当前访问到的元素,也可以理解为等于区间的最后一位,gt表示大区间的第一位。这次的partition操作将比较分为三种情况:

  1. 小于分区点

我们需要将lt + 1i进行交换,并将lti依次进行后移。因为lt表示为小区间的最后一位,所以lt + 1就表示等于区间的第一个元素,而此时i又小于区间值,所以交换后lt依然是小区间的最后一位,而i继续遍历下一个元素。

  1. 大于分区点

我们需要将gt - 1i进行交换,因为gt表示的是当前大区间的第一位,而gt - 1则表示最红等于区间的最后一位,交换位置之后,大区间的范围也就增加了。此时仅仅gt前移一位即可,i不需要移动,因为交换过去的值还不确定它的大小,正好作为当前元素即可。

  1. 等于分区点 那么i + 1即可,增加等于区间的范围及遍历下一个元素,lt/gt坐标都不需要移动。最终igt碰上之后结束遍历过程。

代码如下:

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问题时与堆处理的优劣(还有尾递归的优化,貌似浏览器不支持,就不列出了)。完全理解快排也算是打通了算法的任督二脉,为更难理解的算法打好基础。作为排序里面的明星算法,快排值得一整个章节。

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 前端学数据结构与算法(七): 从零实现优先队列-堆及其应用

    为什么说树结构是01世界里最重要的数据结构,因为只要调整一下节点的存储顺序或枝杈多少,解决问题的类型就可以完全不同。本章介绍的堆也是二叉树的一种,与二叉搜索树想...

    飞跃疯人院
  • 前端学数据结构与算法(十一):看似简单又让人抓狂的二分查找算法

    二分查找法是一种高效的查找算法,它的思想非常好理解,但编写正确的二分查找并不简单。本章从最基础的二分查找实现开始,讲解其编写技巧,接下来介绍它的四个常见变种的编...

    飞跃疯人院
  • 前端学数据结构与算法(九):常见五种排序算法的实现及其优缺点

    数据结构章节暂时告一段落,从这一章节开始算法之旅。首先从排序开始,排序作为最基础的算法,一点也不简单,写一个快排、堆排、归并排序在大厂面试中并不罕见,或者某些题...

    飞跃疯人院
  • 前端面试题解密:经典算法之冒泡算法(ES6版)及优化

    随着前端的飞速发展,前端业务开发给前端工程师提出了更高的要求,因而算法题也越来越高频次的出现在前端面试中。有很多的小伙伴找胡哥苦诉,在前端实际开发中(除了涉及游...

    胡哥有话说
  • PHP 笔试 + 面试题

    本章主要介绍常见的 PHP 笔试 + 面试题,包括: ---- 基础及程序题 数据库技术题 综合技术题 项目及设计题 ---- 基础及程序题 [1] 写一...

    echobingo
  • [数据结构与算法] 排序算法之选择排序和堆排序

    选择排序(select sorting)也是一种简单的排序方法。它的基本思想是: 第一次从arr[0]~arr[n-1]中选取最小值,与arr[0]交换, ...

    时间静止不是简史
  • 快速排序(quick sort)C++实现

    每次选一个轴pivot(我选数组的第一个元素arr[p]),遍历其余数组元素使得比arr[p]大的数都在arr[p]的右边,比arr[p]小的数都在arr[p]...

    kalifa_lau
  • PHP四种排序算法(选择排序)

    阿沐
  • 【追求极致】我是如何把easy级别的算法题做成hard级别的。

    2、如果你懂某些算法思想,这道题很简单,如果不懂,那么这道题顿时很难,例如有些需要dp来处理的。

    帅地
  • PHP四种排序算法(插入排序)

    阿沐

扫码关注云+社区

领取腾讯云代金券