数据结构与算法系列

数据结构与算法系列(5)--归并排序

上一篇文章展示了4个容易理解的排序算法，这一篇继续讲述另一个排序算法—归并排序

归并排序

归并排序的核心思想就是分治，将一个数组拆分成2个小的数组，进行排序，排序完后进行合并

如果将元素分解到每个数组只有一个或者零个元素后，就不需要进行排序，直接进行合并就行了

自顶向下归并排序

归并排序可以自顶向下进行排序，也可以自底向上进行排序，两个的效率都差不多，其中自顶向下的排序的实现，是很典型的递归实现。是十分经典的分治

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
function mergeSort_top2bottom(arr, start, end){
    if (start === undefined && end === undefined){
        start = 0
        end = arr.length - 1
    }

    let cha = []
    function merge(arr, left, mid, right){
        let i = left, j = mid + 1

        for (let q = left; q <= right; q++){
            cha[q] = arr[q]
        }

        for (let q = left; q <= right; q++){
            if (i > mid) arr[q] = cha[j++]
            else if (j > right) arr[q] = cha[i++]
            else if (cha[i] <= cha[j]) arr[q] = cha[i++]
            else arr[q] = cha[j++]
        }
    }
    
    let len = end - start
    if (len <= 0) return

    let mid = parseInt((end + start) / 2)
    mergeSort_top2bottom(arr, start, mid)
    mergeSort_top2bottom(arr, mid + 1, end)
    merge(arr, start, mid, end)

    return arr
}

自底向上的归并排序

自底向上就是从长度为1的小数组开始，然后2,4,8,16…这样想上归并，最后形成一个大数组

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
function mergeSort_bottom2top(arr){
    let cha = []
    function merge(arr, left, mid, right){
        let i = left, j = mid + 1

        for (let q = left; q <= right; q++){
            cha[q] = arr[q]
        }

        for (let q = left; q <= right; q++){
            if (i > mid) arr[q] = cha[j++]
            else if (j > right) arr[q] = cha[i++]
            else if (cha[i] <= cha[j]) arr[q] = cha[i++]
            else arr[q] = cha[j++]
        }
    }

    let length = arr.length
    for (let base = 1; base >= arr.length; base *= 2){
        for (let i = 0; i < length; i = i + base * 2){
            merge(arr, i, i + base, Math.min(i + base * 2 - 1, length - 1))
        }
    }

    return arr
}

算法属性

最优时间复杂度 平均时间复杂度 最差时间复杂度 空间复杂度 稳定性
Ω(nlogn) Θ(nlogn) O(nlogn) O(n) 稳定

分治算法还可以进行进一步的优化

  1. 对小规模子数组使用插入排序

    归并排序使用递归的方式，在数组较小的时候频繁的递归调用函数对性能影响较大，所以当子数组的规模较小时，可以尝试使用其他排序算法(插入排序，选择排序)对子串进行排序，提升效率

  2. 通过将排序数组和复制属性的身份互换的形式，减少复制数据的次数

END

2019-02-27 修复错误的算法复杂度

2019-02-25 完成

2019-02-25 立项