插入排序

定义

插入排序是一种简单的排序算法，它通过逐个元素地构建最终排序好的数组。它使用比较来找到当前元素应该插入的正确位置，以保持已排序的子数组。

实现

• 使用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]

复杂度

该算法的平均时间复杂度为O(n^2)，其中n是输入数组的大小。