基本排序算法-归并排序

发表于 分类于

归并排序

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
/*
 * @Description: mergeSort
 * @Author: libk
 * @Github: https://github.com/libk
 */
function mergeSort (arr) {
  if (arr === null || arr === undefined || arr.length <= 1) {
    return arr
  }
  const mid = Math.floor(arr.length / 2)
  const leftArr = arr.slice(0, mid)
  const rightArr = arr.slice(mid, arr.length)
  mergeSort(leftArr)
  mergeSort(rightArr)
  merge(arr, leftArr, rightArr)
}

function merge (arr, left, right) {
  let i = 0
  let iL = 0
  let iR = 0

  while (iL < left.length && iR < right.length) {
    arr[i++] = (left[iL] < right[iR]) ? left[iL++] : right[iR++]
  }

  while (iL < left.length) {
    arr[i++] = left[iL++]
  }
  while (iR < right.length) {
    arr[i++] = right[iR++]
  }
}

用归并排序的思想解决小和问题

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
37
38
/*
 * @Description: getSmallSum
 * @Author: libk
 * @Github: https://github.com/libk
 */
function getSmallSum (arr) {
  if (arr === null || arr === undefined || arr.length <= 1) {
    return 0
  }

  const mid = Math.floor(arr.length / 2)
  const leftArr = arr.slice(0, mid)
  const rightArr = arr.slice(mid, arr.length)
  return getSmallSum(leftArr) + getSmallSum(rightArr) + merge(arr, leftArr, rightArr)
}

function merge (arr, left, right) {
  let sum = 0
  let i = 0
  let iL = 0
  let iR = 0

  while (iL < left.length && iR < right.length) {
    if (left[iL] < right[iR]) {
      sum += left[iL] * (right.length - iR)
      arr[i++] = left[iL++]
    } else {
      arr[i++] = right[iR++]
    }
  }
  while (iL < left.length) {
    arr[i++] = left[iL++]
  }
  while (iR < right.length) {
    arr[i++] = right[iR++]
  }
  return sum
}