Skip to content

Latest commit

 

History

History
86 lines (61 loc) · 2.09 KB

每日一算法：归并排序.md

File metadata and controls

86 lines (61 loc) · 2.09 KB
Raw

每日一算法：归并排序

归并排序（Merge sort）是一种使用“分而治之”概念的排序算法。

作为一种典型的分而治之思想的算法应用，归并排序的实现有两种方法：

  • 自上而下的递归（所有递归的方法都可以用迭代重写，所以就有了第 2 种方法）
  • 自下而上的迭代

归并只做两件事：

  • 把它的输入分成几个小节，直到每个小节只剩下一个元素。
  • 将其所有子部分合并（并排序）为一个现在已排序的大部分。

假设我们的数组是这样的：

[4, 3, 1, 2]

我们首先将数组分成 2 个数组：

[4, 3]
[1, 2]

然后我们递归地划分这些数组：

[4]
[3]

和

[1]
[2]

然后，通过对这些元素进行排序来构造结果：

[3, 4]
[1, 2]

然后我们合并这两个数组：

[1, 2, 3, 4]

JavaScript 实现

使用归并排序算法对数字数组进行排序。

  • 使用递归。
  • 如果 length 数组的小于 2，则返回数组。
  • 使用 Math.floor() 计算数组的中间点。
  • 使用 Array.prototype.slice() 将数组一分为二，并在创建的子数组上递归调用 mergeSort()。
  • 最后，使用 Array.from() 和 Array.prototype.shift() 将两个排序后的子数组合并为一个。
const mergeSort = (arr) => {
  if (arr.length < 2) return arr
  const mid = Math.floor(arr.length / 2)
  const l = mergeSort(arr.slice(0, mid))
  const r = mergeSort(arr.slice(mid, arr.length))
  return Array.from({ length: l.length + r.length }, () => {
    if (!l.length) return r.shift()
    else if (!r.length) return l.shift()
    else return l[0] > r[0] ? r.shift() : l.shift()
  })
}

mergeSort([5, 1, 4, 2, 3]) // [1, 2, 3, 4, 5]

此示例来自 30 seconds of code 的 mergeSort

更多资料