JavaScript 实现归并排序的常见陷阱与修复指南-js教程-PHP中文网

JavaScript 实现归并排序的常见陷阱与修复指南

本文详解 javascript 中归并排序失效的根本原因：变量作用域缺失、数组引用误用、边界复制错误及低效取整操作，并提供可直接运行的修正代码与关键注意事项。

本文详解 javascript 中归并排序失效的根本原因：变量作用域缺失、数组引用误用、边界复制错误及低效取整操作，并提供可直接运行的修正代码与关键注意事项。

归并排序是一种经典的分治（Divide-and-Conquer）排序算法，其核心逻辑在 Java 等强类型语言中易于实现，但在 JavaScript 中若忽略语言特性，极易因隐式全局变量、引用赋值和数组操作细节导致“看似递归、实则失效”的问题。原始代码仅对部分元素排序（如输出 [7, 6, 5, 4, 3, 2, 1, 8]），本质是递归子问题未真正合并回原数组，导致上层 merge 调用始终基于未更新的数据进行合并。

? 核心问题剖析

全局变量污染（最隐蔽且致命）
原代码中 k = 0、q = 0、w = lb 等声明缺少 let/const，使 k、q、w 成为全局变量。在多层递归调用中，它们被反复覆盖，导致索引错乱、数据写入位置错误。
数组引用而非拷贝
let sorted_arr = arr 并未创建新数组，而是让两个变量指向同一内存地址。后续 sorted_arr[w] = b[q] 实际修改的是 arr，但 sort 函数末尾的复制逻辑本身存在缺陷（见第4点），进一步加剧混乱。

错误的回写逻辑（关键缺陷）
原 for 循环：

for (q = 0, w = lb; q <p>表面看是将临时数组 <code>b</code> 复制回目标区间，但循环中 <code>q</code> 是全局变量，且 <code>w</code> 从 <code>lb</code> 开始递增——这本应正确。然而，<strong>更严重的问题在于：<code>sort</code> 函数应修改传入的 <code>arr</code>，而非依赖外部 <code>sorted_arr</code></strong>。当前设计割裂了数据流，使递归合并失去一致性。</p>

低效且易出错的中点计算
parseInt((hb + lb) / 2) 先转字符串再解析，性能差且语义不清；推荐位运算 Math.floor((lb + hb) / 2) 或 ((lb + hb) >> 1)（适用于非负整数索引）。

Alibabacloud Sdk Client Initialization For Java
在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。

下载

✅ 正确实现：就地排序 + 局部变量 + 清晰数据流

以下为修复后的完整可运行代码，采用原地排序（in-place） 设计，所有操作均作用于输入数组 arr，彻底消除引用歧义：

function mergeSort(arr, lb = 0, hb = arr.length - 1) {
  if (lb >= hb) return;

  const mid = Math.floor((lb + hb) / 2); // 或 (lb + hb) >> 1
  mergeSort(arr, lb, mid);
  mergeSort(arr, mid + 1, hb);
  merge(arr, lb, mid, hb);
}

function merge(arr, lb, mid, hb) {
  // 创建临时数组存储合并结果
  const temp = [];
  let i = lb, j = mid + 1, k = 0;

  // 合并两个有序子数组
  while (i <h3>⚠️ 关键注意事项</h3>

永远使用 let/const 显式声明变量：避免意外创建全局变量，尤其在递归函数中。
避免“伪拷贝”赋值：let a = b（当 b 是数组或对象）只是引用传递，需用 [...b]、Array.from(b) 或 b.slice() 创建副本。
合并函数必须作用于原数组：merge 的职责是将 [lb, mid] 和 [mid+1, hb] 两段有序数据合并到 arr[lb..hb]，不应依赖外部变量。
测试边界用例：空数组 []、单元素 [42]、已排序数组 [1,2,3]、逆序数组 [3,2,1]，确保鲁棒性。