每日一算法：插入排序.md

每日一算法：插入排序

插入排序就像平时你打牌，将扑克牌从你手的一个部位分类并移动到另一个部位的方法与插入排序的工作原理几乎相同。

原理

1. 假设将数组的第一个数字当做有序序列（已排序），把第二个到最后一个数字当做未排序序列。
2. 从头到尾依次扫描未排序序列，查看其是否小于或大于之前的数字： 2.1 如果活动号码（未排序的数字）大于其左边的数字，则不执行任何操作。现在的顺序是正确的。跳到第 3 步。 2.2 如果活动号码小于其左边的数字，请继续向左移动。继续移动，直到您的活动号码命中另一个值小于它的号码。当遇到这种情况时，把活跃的数字插入到该数字旁边。
3. 用一个新的活动号码重复整个过程。选择下一个未排序的数字，从第 2 步开始重新开始。

如果待插入的数字与有序序列中的某个元素相等，则将待插入数字插入到相等元素的后面。

JavaScript 实现

使用插入排序算法对数字数组进行排序。

• 使用 Array.prototype.reduce() 遍历给定数组中的所有元素。
• 如果 length 累加器的为 0，则向其中添加当前元素。
• 使用 Array.prototype.some() 遍历累加器中的结果，直到找到正确的位置。
• 使用 Array.prototype.splice() 将当前元素插入累加器。

const insertionSort = (arr) =>
  arr.reduce((acc, x) => {
    if (!acc.length) return [x]
    acc.some((y, j) => {
      if (x <= y) {
        acc.splice(j, 0, x)
        return true
      }
      if (x > y && j === acc.length - 1) {
        acc.splice(j + 1, 0, x)
        return true
      }
      return false
    })
    return acc
  }, [])

insertionSort([6, 3, 4, 1]) // [1, 3, 4, 6]

此示例来自 30 seconds of code 的 insertionSort

更多资料

Insertion Sort