归并排序

发表于 | 分类于

基本思想

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。


不错的文章

相关题目

实现

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
/**
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function(num) {
    return helper(num, 0, num.length - 1);
};

function helper(num, lo, hi) {
    //如果lo>=hi，说明到叶子节点了
    if (lo >= hi) {
        return [num[lo]]
    }
    let mid = lo + Math.floor((hi - lo) / 2);
    let leftSorted = helper(num, lo, mid);
    let rightSorted = helper(num, mid + 1, hi);
    return merge(leftSorted,rightSorted);
}
//[1,8],[2,9]
//合并两个有序数组
function merge(aNum, bNum) {
    let res = [];
    while (aNum.length && bNum.length) {
        if(aNum[0]<=bNum[0]){
            res.push(aNum.shift());
        } else {
            res.push(bNum.shift());
        }
    }
    return aNum.length > 0 ? res.concat(aNum) : res.concat(bNum);
}