什么是归并排序?

菜园前端
• 阅读 374

原文链接:https://note.noxussj.top/?source=helloworld


什么是归并排序(mergeSort)?

主要分成两部分实现,分、合操作:

  • 分:把数组分成两半,在递归地对子数组进行 "分" 操作,直到分成一个个单独的数
  • 合:把两个数组合并为有序数组,再对有序数组进行合并,直到全部子数组合并为一个完整数组

归并排序就是采用了分而治之的算法设计思想,另外归并排序其实就像擂台赛一样,每两组进行 pk ,最后到半决赛,总决赛类似。

算法步骤

  1. 通过 Math.floor 将目标数组劈成两半,右边可能会多出来一个
  2. 通过递归的方式对刚才分解出来的数组,再次进行劈成两半操作
  3. 直到劈成数组变成一个为止
  4. 开始进行合并操作,对两个数组进行遍历排序,小的放左边,大的放右边
  5. 一直合并到最大的数组
  6. 排序完成

动画演示链接

https://visualgo.net/zh/sorting

什么是归并排序?

基础案例

  • 时间复杂度:O (n * logn)
  • 空间复杂度:O (1)
Array.prototype.mergeSort = function () {
    const rec = (arr) => {
        if (arr.length === 1) return arr

        const mid = Math.floor(arr.length / 2)
        const left = arr.slice(0, mid)
        const right = arr.slice(mid, arr.length)
        const orderLeft = rec(left)
        const orderRight = rec(right)
        const res = []

        while (orderLeft.length || orderRight.length) {
            if (orderLeft.length && orderRight.length) {
                res.push(orderLeft[0] < orderRight[0] ? orderLeft.shift() : orderRight.shift())
            } else if (orderLeft.length) {
                res.push(orderLeft.shift())
            } else if (orderRight.length) {
                res.push(orderRight.shift())
            }
        }

        return res
    }

    const res = rec(this)

    res.forEach((n, i) => {
        this[i] = n
    })
}

const arr = [5, 4, 3, 2, 1]

arr.mergeSort() // [1, 2, 3, 4, 5]

"分" 时间复杂度是 O (logn),"合" 时间复杂度是 O (n) ,所以整体的时间复杂度为 O (n * logn)。代码中没有借助其他数据结构来存储线性增长的元素,所以空间复杂度为 O (1) 。

点赞
收藏
评论区
推荐文章
22 22
3年前
【排序算法动画解】直接插入排序
本文为系列专题的第14篇文章。1.2.3.4.5.6.7.8.9.10.11.12.13.前面介绍了已经介绍了三种排序,暴力排序、冒泡排序和简单选择排序,一个共同点都是基于交换。我们可以用另一种视角来看待排序,即将一个待排序的数组看成两个部分:有序区和乱序区。在排序开始前,整个数组都是乱序区,而有序区则为空:排序开始后,有序区
九路 九路
4年前
二分查找法的递归和非递归的实现
//二分查找法非递归实现,在一个有序的数组中查找e元素的位置,找不到返回1publicstaticintbinarySearch(intdata,inte){intl0;intrdata.length1;while(l<r){
菜园前端 菜园前端
1年前
什么是函数组合?
原文链接:什么是函数组合?函数组合(Compose),如果一个函数要经过多个函数处理才能得到最终值,这个时候可以把中间过程的函数合并成一个函数。函数组合默认是从右到左执行,每个函数只能接收一个参数,否则需使用柯里化进行转换。作用函数组合可以让我们把细粒度的
Stella981 Stella981
3年前
JavaScript基础知识
题目:1.找出数字数组中最大的元素(使用Math.max函数)2.转化一个数字数组为function数组(每个function都弹出相应的数字)3.给object数组进行排序(排序条件是每个元素对象的属性个数)4.利用JavaScript打印出Fibonacci数(不使用全局变量)5.实现如下语法的功能:vara(5).plus(
Wesley13 Wesley13
3年前
PHP二维数据排序,二维数据模糊查询
一、因为项目中的一个报表需要合并三个表的数据,所以分表查询再合并数据,利用PHP数组函数进行排序,搜索。三表合并后的数组结构如下:Array(0Array(history_id12sla_group_
Wesley13 Wesley13
3年前
PHP快速排序(原地切分)
        快速排序是一种分治的排序算法,采用递归的思想,将数组元素分为两部分,选择切分元素,左右扫描数组,将大于切分元素的数据放在右边,小于切分元素的数据放在左边,直到扫描指针相遇,切分结束,同时递归调用,直到数组有序。      代码如下:<?phpfunctionquick_sort(array&$array,$l
Wesley13 Wesley13
3年前
Java数组的声明与创建
今天在刷Java题的时候,写惯了C发现忘记了Java数组的操作,遂把以前写的文章发出来温习一下。首先,数组有几种创建方式?Java程序中的数组\\必须先进行初始化才可以使用,\\所谓初始化,就是为数组对象的元素分配内存空间,并为每个数组元素指定初始值,而在Java中,数组是静态的,数组一旦初始化,长度便已经确定,不能再随意更改。
菜园前端 菜园前端
1年前
排序和搜索介绍
原文链接:排序和搜索不仅在工作中会经常遇到,在面试中也是高频考点,所以这个是必须要懂的。排序:把某个乱序的数组变成升序或者降序的数组。例如在我们平常开发中,例如要对一个表格进行日期的升序或降序排列。在JavaScript中通常使用数组的sort方法实现。搜
菜园前端 菜园前端
1年前
什么是快速排序?
原文链接:什么是快速排序(quickSort)?主要分成两部分实现,分区、递归操作。分区从数组中任意选择一个"基准",所有比基准小的元素放在基准前面,比基准大的元素放在基本后面。递归递归地对基准前后的子数组进行分区。算法步骤1.首先获取数组的第一个值(作为
京东云开发者 京东云开发者
11个月前
时间复杂度为 O(nlogn) 的排序算法 | 京东物流技术团队
归并排序归并排序遵循分治的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后合并这些子问题的解来建立原问题的解,归并排序的步骤如下:划分:分解待排序的n个元素的序列成各具n/2个元素的两个子序列,将长数组的排序问题转换为短数