JavaScript分治算法_归并排序详解-js教程-PHP中文网

JavaScript分治算法_归并排序详解

夢幻星辰

发布： 2025-11-20 21:36:06

原创

988人浏览过

归并排序通过分治法将数组递归拆分为单个元素后，再逐层合并为有序数组，其核心是分解与合并过程，JavaScript实现包括递归分割和双指针合并两个有序子数组。

javascript分治算法_归并排序详解

归并排序是一种典型的分治算法，通过将数组不断拆分，再逐层合并，最终实现有序排列。它的核心思想是“分而治之”：把一个大问题分解成多个小问题分别解决，再把结果合并起来。

归并排序的基本原理

归并排序分为两个阶段：分解和合并。

分解：将数组从中间一分为二，递归地对左右两部分继续分解，直到每个子数组只有一个元素（单个元素天然有序）。
合并：将两个有序的子数组合并成一个新的有序数组，通过比较元素大小依次放入临时数组中，最后写回原数组。

这个过程保证了每次合并时输入的两个子数组都是有序的，因此可以高效地完成整体排序。

JavaScript实现归并排序

下面是一个清晰、可读性强的归并排序实现：

立即学习“Java免费学习笔记（深入）”；

function mergeSort(arr) {
  // 基本情况：数组长度小于等于1时直接返回
  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++;
    }
  }

  // 将剩余元素合并
  while (i < left.length) {
    result.push(left[i]);
    i++;
  }
  while (j < right.length) {
    result.push(right[j]);
    j++;
  }

  return result;
}

登录后复制

使用示例：

Booltool

常用AI图片图像处理工具箱

140

查看详情

const unsortedArray = [64, 34, 25, 12, 22, 11, 90];
const sortedArray = mergeSort(unsortedArray);
console.log(sortedArray); // [11, 12, 22, 25, 34, 64, 90]

登录后复制