立诚勿怠,格物致知
It's all about connecting the dots

分治法与快速排序

注:图片来源于文章(https://segmentfault.com/a/1190000015316531)

快速排序采用了一种分治的思想,由于排序效率在同为O(N*logN)的几种排序方法中效率较高,因此经常被采用。快速排序是一种不稳定的排序方法。该方法的基本思想是:

  1. 定基准:先从数列中取出一个数作为基准数;
  2. 分区:将比这个数打的数全放到它的右边,小于或等于它的数全放到它的左边;
  3. 再对左右两个区间重复第二步,直到各区间只有一个数(终止条件)。

上面三步中,第一步定基准的方式比较多样化,网上大体有三种方式(具体用哪一种个人觉得没啥差别):

  1. 找数组中位于中间位置的一个数作为基准(参考文章后面的代码实现);
  2. 直接选数组中第一个数作为基准;
  3. 取首尾中三个数的中位数作为基准(参考文章开头的图片)。

递归实现:

function quickSort (arr) {
    // 数组长度小于2就直接返回,不需要再处理了,这个就是快排的终止条件
    if (arr.length <= 1) {
        return arr
    }

    // pivot意思是:枢纽、中心点
    var pivotIndex = Math.floor(arr.length / 2)
    // 找基准,并把基准从原数组中删除
    var pivot = arr.splice(pivotIndex, 1)[0]
    // 定义左右数组
    var left = []
    var right = []

    // 比基准小的放在left,比基准打的放在right
    arr.forEach(function (val) {
        if (val <= pivot) {
            left.push(val)
        } else {
            right.push(val)
        }
    })

    // 递归
    return quickSort(left).concat([pivot], quickSort(right))
}

 

赞(0) 打赏
文章名称:《分治法与快速排序》
文章链接:https://www.orzzone.com/quick-sort.html
商业联系:yakima.public@gmail.com

本站大部分文章为原创或编译而来,对于本站版权文章,未经许可不得用于商业目的,非商业性转载请以链接形式标注原文出处。
本站内容仅供个人学习交流,不做为任何投资、建议的参考依据,因此产生的问题需自行承担。

评论 抢沙发

大前端WordPress主题 更专业 更方便

支持快讯、专题、百度收录推送、人机验证、多级分类筛选器,适用于垂直站点、科技博客、个人站,扁平化设计、简洁白色、超多功能配置、会员中心、直达链接、文章图片弹窗、自动缩略图等...

去看看

觉得文章有用就打赏一下文章作者

非常感谢你的打赏,我们将继续给力提供更多优质内容!

支付宝扫一扫打赏

微信扫一扫打赏

登录

找回密码

注册