Skip to content

归并排序

定义

归并排序是一种高效、通用的基于比较的排序算法。归并排序是一种分治算法,基于将一个数组分解成多个子数组,直到每个子数组只包含一个元素,然后以一种能够得到排序数组的方式将这些子数组合并起来。

实现

  • 使用递归。
  • 如果数组的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]

复杂度

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