2rever的前端小站

js归并排序

Word count: 105 / Reading time: 1 min
2018/10/23 Share

归并排序

  • 第一个工业级别的算法
  • 归并排序没有办法就地排序
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    function mergeSort(ary) {
    if (ary.length < 2) {
    return ary.slice()
    }

    var mid = Math.floor(ary.length / 2)
    var left = mergeSort(ary.slice(0, mid))
    var right = mergeSort(ary.slice(mid))
    var result = []

    while(left.length && right.length) {
    if (left[0] <= right[0]) {
    result.push(left.shift())
    } else {
    result.push(right.shift())
    }
    }

    result.push(...left, ...right)

    return result
    }
CATALOG
  1. 1. 归并排序