js实现归并

归并排序原理

归并排序是一种分治算法，通过递归将数组拆分为最小单元（单元素），再按顺序合并有序子数组。其核心是分解和合并两个操作，时间复杂度为 O(n log n)，空间复杂度为 O(n)。

实现步骤

分解阶段 将数组不断二分，直到子数组长度为1。递归调用分解函数：

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

合并阶段 合并两个有序数组时，使用双指针逐个比较元素：

function merge(left, right) {
  let result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  return result.concat(left.slice(i)).concat(right.slice(j));
}

完整代码示例

function mergeSort(arr) {
  if (arr.length <= 1) return arr;

  const mid = Math.floor(arr.length / 2);
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));

  return merge(left, right);
}

function merge(left, right) {
  let result = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] < right[j]) {
      result.push(left[i]);
      i++;
    } else {
      result.push(right[j]);
      j++;
    }
  }

  return [...result, ...left.slice(i), ...right.slice(j)];
}

// 使用示例
const array = [5, 3, 8, 4, 2];
console.log(mergeSort(array)); // 输出 [2, 3, 4, 5, 8]

关键点说明

• 稳定性：归并排序是稳定排序，相等元素的相对位置不变。
• 空间消耗：合并时需要临时数组，非原地排序。
• 优化方向：对小规模子数组可改用插入排序减少递归开销。

可视化过程

以数组 [5, 3, 8, 4, 2] 为例：

1. 分解为 [5,3] 和 [8,4,2]
2. 继续分解至单元素
3. 逐步合并为 [3,5] 和 [2,4,8]
4. 最终合并为 [2,3,4,5,8]