面试题 - 前端 - 算法 - 排序 - 归并排序

发表于 分类于 阅读次数：

归并排序是一种分而治之算法。其思想是将原始数组切分成较小的数组，直到每个小数组只 有一个位置，接着将小数组归并成较大的数组，直到最后只有一个排序完毕的大数组。

归并排序

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
function mergeSort(array) {
    if (array.length > 1) {
        const {
            length
        } = array;
        const middle = Math.floor(length / 2);
        const left = mergeSort(array.slice(0, middle));
        const right = mergeSort(array.slice(middle, length));
        array = merge(left, right);
    }
    return array;
}

function merge(left, right ) {
    let i = 0;
    let j = 0;
    const result = [];
    while (i < left.length && j < right.length) {
        result.push(
            left[i] < right[j] ? left[i++] : right[j++]
        );
        console.log(result)
        //先push ，再++
    }
    return result.concat(i < left.length ? left.slice(i) : right.slice(j));
}

const arr = [9, 3, 7, 4, 6];

console.log(mergeSort(arr));