# 归并排序

公司: 牛客网,几种常见时间复杂度比较低的排序算法之一

leetcode:912:排序树组题链

给你一个整数数组 nums,请你将该数组升序排列。

# 原理

归并排序利用了分治的思想来对序列进行排序。对一个长为 n 的待排序的序列,我们将其分解成两个长度为n/2的子序列。每次先递归调用函数使两个子序列有序,然后我们再线性合并两个有序的子序列使整个序列有序。

# 相关属性

  • 递归实现
    • 缺点:
      • 容易爆栈,当数组足够大,递归很深
      • 需要额外的内存空间
    • 优点
      • 性能不受输入数据的影响,始终都是 O(nlogn) 的时间复杂度
      • 稳定的排序算法

# 递归实现

/**
 * 归并排序
 * @param {Array<number>} arr 
 */
function mergeSort(arr) {
    const len = arr.length
    // 无需排序
    if (len < 2) {
        return arr
    }
    const mid = len >> 1 // 右移一位 === 除2并向下取整
    return merge(mergeSort(arr.slice(0, mid)), mergeSort(arr.slice(mid)))
}

/**
 * 合并
 * @param {Array<number>} left 
 * @param {Array<number>} right 
 */
function merge(left, right) {
    const res = []
    let i = 0, j = 0
    while (i < left.length && j < right.length) {
        res.push(left[i] <= right[j] ? left[i++] : right[j++])
    }

    while (i < left.length) {
        res.push(left[i++])
    }

    while (j < right.length) {
        res.push(right[j++])
    }

    return res
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

# 迭代实现

//TODO: ... 未完待续
1