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

JavaScript 实现归并排序的常见错误与修复指南

本文详解 javascript 中归并排序失效的根本原因：变量作用域缺失、数组引用混淆、边界拷贝错误及低效取整，提供可直接运行的修正代码，并强调递归合并逻辑中「原地覆盖」的关键原则。

本文详解 javascript 中归并排序失效的根本原因：变量作用域缺失、数组引用混淆、边界拷贝错误及低效取整，提供可直接运行的修正代码，并强调递归合并逻辑中「原地覆盖」的关键原则。

归并排序是一种经典的分治（Divide-and-Conquer）排序算法，其核心在于递归拆分 + 有序合并。虽然算法思想语言无关，但在 JavaScript 中直接移植 Java 版本时极易因语言特性差异导致失败——正如示例代码所示：仅首元素被“移动”，其余未排序。根本问题不在逻辑，而在 JavaScript 的变量作用域、引用语义和类型处理细节。

? 主要错误分析

全局变量污染（严重隐患）
原代码中 k = 0、q = 0、w = lb 等未加 let/const 声明，导致这些变量成为隐式全局变量。在多层递归调用中，k、q、w 被反复覆盖，破坏合并索引的正确性。✅ 正确做法：所有循环变量必须显式声明为块级作用域变量（let k = 0）。

数组引用误用（逻辑断裂）
let sorted_arr = arr 并未创建副本，而是让两个变量指向同一内存地址。后续 sorted_arr[w] = b[q] 实际修改的是 arr，但 sort() 函数末尾的拷贝逻辑存在致命笔误：

for (i = 0; i <p>正确应为 <code>b[i]</code>，且必须将临时数组 <code>b</code> 的内容<strong>回填到原数组 <code>arr</code> 的 <code>[lb, hb]</code> 区间内</strong>，否则上层递归无法获取已排序子段。</p><div class="aritcle_card flexRow artxards">
											<div class="artcardd flexRow">
												<a class="aritcle_card_img" rel="nofollow" href="/xiazai/skill3430" title="Alibabacloud Sdk Client Initialization For Java"><img
														src="https://img.php.cn/upload/skill/000/000/081/178955835420587.jpg" alt="Alibabacloud Sdk Client Initialization For Java" onerror="this.onerror='';this.src='/static/lhimages/moren/morentu.png'" ></a>
												<div class="aritcle_card_info flexColumn">
													<a rel="nofollow" href="/xiazai/skill3430" title="Alibabacloud Sdk Client Initialization For Java" class="overflowclass">Alibabacloud Sdk Client Initialization For Java</a>
													<p class="overflowclass">在 Java 中初始化和管理阿里云 SDK客户端。包括单例模式、线程安全、endpoint 与 region 配置、VPC 终端节点、同步与异步等。</p>
												</div>
												<a rel="nofollow" href="/xiazai/skill3430" title="Alibabacloud Sdk Client Initialization For Java" class="aritcle_card_btn flexRow flexcenter"><b></b><span>下载</span>
												</a>
											</div>
										</div>

取中位数低效且易错
parseInt((hb + lb) / 2) 先转字符串再解析，性能差；更严重的是，当 lb 和 hb 为负数（虽本例不出现）时行为不可靠。✅ 推荐位运算：Math.floor((lb + hb) / 2) 或高效写法 (lb + hb) >> 1（仅适用于非负整数索引）。
缺少关键合并步骤的“就地更新”保障
归并排序要求每次 sort() 执行后，arr[lb..hb] 必须是已排序的。原代码试图写入 sorted_arr，但 sorted_arr === arr，而拷贝逻辑又出错，导致子数组始终未真正合并。

✅ 修复后的完整可运行代码

function merge(arr, lb, hb) {
  if (lb >= hb) return;
  const mid = Math.floor((lb + hb) / 2); // 更安全，兼容所有整数
  merge(arr, lb, mid);
  merge(arr, mid + 1, hb);
  mergeSortStep(arr, lb, mid, hb);
}

function mergeSortStep(arr, lb, mid, hb) {
  const left = arr.slice(lb, mid + 1);   // 复制左半段
  const right = arr.slice(mid + 1, hb + 1); // 复制右半段

  let i = 0, j = 0, k = lb;

  // 归并到原数组 arr[lb..hb]
  while (i <h3>? 关键实践建议</h3>