归并排序 - wangshengliang

核心思想#

归并排序，英语 Merge Sort，这是一种基于 分治法 的排序算法。它的基本思想是将一个大的数组分成若干个小的数组，直到每个小数组只有一个元素为止。然后再将这些小数组合并成一个有序的数组。

归并排序工作流程：

分割：将原始数组分成两个部分，递归的将每一个部分的数组继续分割，直到每个部分只包含一个元素。

合并：将分割好的部分，两两合并，合并的时候保持顺序，最终合并成一个有序的数组。

“拆分”非常好理解，每次砍一半。

关键是“合并”，究竟是如何合并成有序的？

合并过程#

那么这里以最后一步为例：[4, 5, 7, 8] 和[1, 2, 3, 6] 进行合并

定义两个指针，第一个指向第一个有序数组的第一个元素；第二个指向第二个有序数组的第一个元素。需要创建一个临时数组，临时数组的长度 = 两个数组长度之和。两个有序数组的第一个元素进行比较，谁小，谁就放入到临时数组的一个元素位置

放入临时数组之后，j 右移指向第二个有序数组的第二个元素。
继续 i 和 j 对应的元素进行比较，4 和 2 比较，仍然是 2 比较小，将 2 放入到 temp 数组的第二个元素的位置。

接下来 j 继续往右边移动，指向第二个有序数组的第三个元素。
继续 i 和 j 对应的元素进行比较，4 和 3 比较，仍然是 3 比较小，将 3 放入到 temp 数组的第三个元素的位置。

接下来 j 继续往右边移动，指向第二个有序数组的第四个元素。
继续 i 和 j 对应的元素进行比较，这一次就是 4 和 6 进行比较，这一次是 4 是比较小，将 4 放入到 temp 数组的第四个元素的位置

接下来就是 i 继续往右边移动，指向第一个有序数组的第二个元素。
继续 i 和 j 对应的元素进行比较，这一次是 5 和 6 进行比较，这一次是 5 是比较小，将 5 放入到 temp 数组的第五个元素的位置

接下来就是 i 继续往右边移动，指向第一个有序数组的第三个元素。
接下来继续上面的操作，这一次是 7 和 6 进行比较，6 比较小，将 6 放入到 temp 数组的第六个元素的位置

这一次应该是 j 往右边移动。但是这一次 j 已经无法往右边移动。说明第二个有序数组所有的元素已经遍历结束。
只需要将第一个有序数组的剩余元素，全部放入到 temp 数组里面即可
最后，再将 temp 这个临时数组里面所有的元素拷贝到原数组中，合并结束

代码实现#

// 这个方法负责合并
function merge(left, right) {
  let result = [] // 临时数组
  let leftIndex = 0 // 左数组的索引，默认指向第一个元素
  let rightIndex = 0 // 右数组的索引，默认指向右数组的第一个元素

  while (leftIndex < left.length && rightIndex < right.length) {
    // 里面就判断究竟是左边数组的元素小还是右边数组元素小
    // 将小的元素放入到临时数组里面
    if (left[leftIndex] <= right[rightIndex]) {
      // 说明左边的元素更小
      // 将左边元素放入到临时数组里面
      result.push(left[leftIndex])
      leftIndex++
    } else {
      // 说明右边元素更小
      // 将右边元素放入到临时数组里面
      result.push(right[rightIndex++])
    }
  }

  // 代码来到这里，说明 left 或者 right 总之有一边已经结束了
  // 将另外一个数组剩余的所有元素放入到临时数组里面
  if (leftIndex < left.length) {
    // 说明左边数组有剩余
    result = result.concat(left.slice(leftIndex))
  }

  if (rightIndex < right.length) {
    // 说明右边数组有剩余
    result = result.concat(right.slice(rightIndex))
  }

  return result
}

// 这个方法主要是负责拆
function mergeSort(arr) {
  if (arr.length < 2) {
    // 如果进入此分支，说明数组不能够再拆了，该数组已经是单独的一个元素了
    // 直接返回该数组
    // 这个其实就是递归的出口
    return arr
  }

  // 如果没有进入上面的 if，那么就需要拆分数组，就是对半分
  const mid = Math.floor(arr.length / 2)

  // 根据上面计算出来的中间值，将整个数组分为左半部分和右半部分
  const left = mergeSort(arr.slice(0, mid))
  const right = mergeSort(arr.slice(mid))

  // 下一步，就是合并左右两个子数组
  return merge(left, right)
}

const arr = [38, 27, 43, 3, 9, 82, 10]
const sortedArr = mergeSort(arr)
console.log(sortedArr)

复杂度#

时间复杂度：O(nlogn)
空间复杂度：O(n)，因为在归并排序中，需要额外的空间来存储临时数组用于合并操作。

稳定性#

归并排序是一种稳定排序。

如果遇到相等的元素，是优先将左边数组的元素放入临时数组。

if (left[leftIndex] <= right[rightIndex]) {
  // 说明左边的元素更小
  // 将左边元素放入到临时数组里面
  result.push(left[leftIndex])
  leftIndex++
} else {
  // 说明右边元素更小
  // 将右边元素放入到临时数组里面
  result.push(right[rightIndex++])
}

关键就是 left[leftIndex] <= right[rightIndex]，因此在左右数组元素相等的情况下，优先放入左边数组的元素。

假设修改一下 left[leftIndex] < right[rightIndex]，这么一改，就变成优先取右边数组的元素放入临时数组，就会导致不稳定。

-EOF-