JavaScript归并排序实现：常见陷阱与优化指南

本文深入探讨了JavaScript归并排序（Merge Sort）实现中常见的几个关键错误，包括归并操作中临时数组回写时的索引错位、边界参数`right`的语义不一致以及次优的中间点计算方式。通过详细分析问题并提供优化后的代码示例，旨在帮助开发者构建健壮、高效且符合JavaScript编程习惯的归并排序算法。

理解归并排序的基本原理

归并排序（Merge Sort）是一种高效的、稳定的排序算法，其核心思想是“分而治之”。它将一个大问题分解为若干个小问题，然后将小问题的解合并起来得到大问题的解。具体到排序，就是：

1. 分解（Divide）: 将待排序数组递归地分解为两个子数组，直到每个子数组只包含一个元素（单个元素被认为是已排序的）。
2. 解决（Conquer）: 对每个子数组进行排序（实际上，分解到单个元素时，这一步是隐式的）。
3. 合并（Combine）: 将两个已排序的子数组合并成一个更大的已排序数组。这个合并操作是归并排序的关键。

原始实现中的问题分析

在给定的JavaScript归并排序代码中，存在几个关键问题导致其无法正常工作并产生 undefined 值。

1. 归并操作中临时数组回写时的索引错误

这是导致输出 [undefined, undefined, ..., 3, 5] 的直接原因。在 merge 函数的最后一步，将 temp 数组中的排序结果拷贝回原数组 arr 时，使用了错误的索引逻辑：

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

// 原始错误代码段
for (let i = left; i <= right; i++) {
    arr[i] = temp[i]; // 错误：temp数组是从索引0开始填充的
}

temp 数组是从索引 0 开始填充的，其有效元素范围是 0 到 k-1。然而，上述代码却尝试使用 arr 的原始索引 i（从 left 到 right）来访问 temp 数组。当 left 不为 0 时，temp[left] 可能越界（undefined），或者访问到 temp 中不正确的位置。

先见AI

数据为基，先见未见

95

查看详情

修正方案： 正确的回写逻辑应该将 temp 数组中的元素从其起始位置 0 开始，依次拷贝到 arr 数组中从 left 开始的位置。

// 正确的临时数组回写逻辑
for (let idx = 0; idx < k; idx++) {
    arr[left + idx] = temp[idx];
}

这里，idx 用于遍历 temp 数组的有效范围 [0, k-1]，而 left + idx 则确保这些元素被放置到 arr 数组中正确的起始位置。

2. right 参数语义不一致及初始调用错误

在许多编程语言和库中，处理数组或列表的范围时，有两种常见的索引约定：

• 闭区间 [left, right]: left 和 right 都包含在范围内。
• 半开区间 [left, right): left 包含在范围内，而 right 是范围的结束点，但不包含在范围内（即“超尾”索引）。

原始代码的 mergesort 函数内部，循环条件如 i <= mid 和 j <= right 表明 right 被视为闭区间。然而，在初始调用 mergesort(arr, 0, n) 时，n 是数组的长度，这意味着 right 被当做超尾索引（arr.length）。这种不一致导致：

• 当 right 作为数组长度传入时，arr[right] 会尝试访问数组越界的位置，可能导致 undefined。
• mid 的计算方式也需要与 right 的语义保持一致。

最佳实践： 在JavaScript等语言中，将 right 参数定义为半开区间的“超尾”索引（即不包含在范围内的第一个索引）是更常见和推荐的做法。这与 Array.prototype.slice() 等内置方法的行为一致，并且简化了循环条件（通常从 i <= right 变为 i < right）。

如果采用半开区间语义：

• mergesort(arr, 0, arr.length) 是正确的初始调用。
• mergesort 和 merge 函数内的所有循环条件都应使用 < 而非 <= right 或 <= mid。
• 递归调用 mergesort(arr, left, mid) 和 mergesort(arr, mid, right) 也符合半开区间语义。

3. 中间点计算与冗余拷贝优化

• 中间点 mid 的计算： 原始代码使用 let mid = parseInt((right - left) / 2) + left; 来计算中间点。使用 parseInt 和浮点除法再转换的方式效率较低。 优化： 使用位运算 >> 1 进行整数除法更高效：let mid = left + ((right - left) >> 1);。

• merge 函数中的冗余拷贝： 原始 merge 函数在主 while 循环结束后，有两个 for 循环用于拷贝剩余元素：

  for (; i <= mid; i++) { temp[k] = arr[i]; k++; }
  for (; j <= right; j++) { temp[k] = arr[j]; k++; }

  登录后复制

  在采用半开区间语义的 merge 逻辑中，如果 i 已经达到 mid，说明左半部分已处理完毕，剩余的元素都在右半部分。如果 j 已经达到 right，说明右半部分已处理完毕，剩余的元素都在左半部分。 一个常见的优化是：当其中一个子数组的所有元素都已拷贝到 temp 后，如果另一个子数组还有剩余元素，这些剩余元素本身就已经是排序好的，并且它们在原数组中的位置相对于已合并的部分是正确的。因此，只需将未完全拷贝的那个子数组的剩余元素拷贝到 temp 即可。在某些实现中，甚至可以省略拷贝右半部分剩余元素到 temp 的步骤，因为它们在原数组中的相对顺序已经正确，后续的 temp 回写操作会覆盖 arr[left] 到 arr[left+k-1] 的部分，而 arr[j] 之后的元素保持不变。

改进后的归并排序实现

综合上述分析和优化，以下是修正并遵循JavaScript惯例的归并排序实现：

/**
 * 归并排序主函数
 * @param {Array<number>} arr 待排序数组
 * @param {number} left 数组范围的起始索引 (包含)
 * @param {number} right 数组范围的结束索引 (不包含, 超尾)
 */
function mergesort(arr, left, right) {
    // 当子数组长度大于1时才需要排序
    if (right - left > 1) {
        // 计算中间索引，使用位运算进行高效的整数除法
        // mid 将是左半部分的超尾索引，也是右半部分的起始索引
        let mid = left + ((right - left) >> 1);

        // 递归排序左半部分 [left, mid)
        mergesort(arr, left, mid);
        // 递归排序右半部分 [mid, right)
        mergesort(arr, mid, right);

        // 合并两个有序子数组
        merge(arr, left, mid, right);
    }
}

/**
 * 合并两个有序子数组
 * @param {Array<number>} arr 原数组
 * @param {number} left 左子数组的起始索引
 * @param {number} mid 左子数组的超尾索引，也是右子数组的起始索引
 * @param {number} right 右子数组的超尾索引
 */
function merge(arr, left, mid, right) {
    let i = left,      // 左子数组的当前索引
        j = mid,       // 右子数组的当前索引
        k = 0;         // 临时数组的当前索引
    let temp = [];     // 临时数组用于存储合并结果

    // 比较并合并左右两个子数组的元素，直到其中一个子数组遍历完毕
    while (i < mid && j < right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    // 将左半部分剩余元素拷贝到临时数组
    // 如果左半部分还有剩余，说明右半部分已经全部拷贝
    while (i < mid) {
        temp[k++] = arr[i++];
    }

    // 注意：如果右半部分有剩余（即 j < right），
    // 它们已经相对有序地存在于原数组中，并且在合并后的结果中，
    // 这些元素将位于 temp 数组回写操作覆盖范围之外，
    // 或者它们会被 temp 数组的

以上就是JavaScript归并排序实现：常见陷阱与优化指南的详细内容，更多请关注php中文网其它相关文章！