归并排序陷阱与优化技巧解析

本篇文章主要是结合我之前面试的各种经历和实战开发中遇到的问题解决经验整理的，希望这篇《归并排序实现陷阱与优化技巧》对你有很大帮助！欢迎收藏，分享给更多的需要的朋友学习~

本文深入探讨了JavaScript归并排序实现中常见的错误和优化点，包括`merge`函数中结果数组回写逻辑的修正、`right`参数边界定义的统一（建议采用左闭右开区间）、高效整数除法的应用，以及如何编写更简洁、更符合JavaScript习惯的归并排序代码。通过分析原始问题代码并提供优化方案，旨在帮助开发者构建健壮且高效的归并排序算法。

归并排序概述

归并排序（Merge Sort）是一种基于分治思想的高效稳定排序算法。其基本思想是将待排序序列递归地分成两半，直到每个子序列只包含一个元素（自然有序），然后将这些子序列两两合并，每次合并都使子序列有序，直到最终合并成一个完整的有序序列。归并排序的时间复杂度为O(n log n)，空间复杂度为O(n)。

常见实现问题与分析

在实现归并排序时，开发者常会遇到一些细节问题，导致代码无法正常工作或效率低下。以下是对一个典型JavaScript归并排序实现中存在问题的详细分析：

原始代码片段

function mergesort(arr, left, right) {
    if (left < right) {
        let mid = parseInt((right - left) / 2) + left;
        mergesort(arr, left, mid);
        mergesort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }
}

function merge(arr, left, mid, right) {
    let i = left, j = mid + 1, k = 0, temp = [];
    while (i <= mid && j <= right) {
        if (arr[i] <= arr[j]) {
            temp[k] = arr[i];
            i++;
            k++;
        } else {
            temp[k] = arr[j];
            j++;
            k++;
        }
    }
    for (; i <= mid; i++) {
        temp[k] = arr[i];
        k++;
    }
    for (; j <= right; j++) {
        temp[k] = arr[j];
        k++;
    }
    for (let i = left; i <= right; i++) { // 问题所在
        arr[i] = temp[i]; // 错误：这里应该是temp[i - left]或使用单独的索引
    }
}

let arr = [ 5, 3, 7, 2, 9, 12, 4 ];
n = arr.length;
mergesort(arr, 0, n); // 问题所在：right参数通常指最后一个元素的索引，而不是数组长度

问题点一：merge函数中结果数组的回写错误

这是导致输出结果异常（如[undefined, undefined, ..., 3, 5]）的核心问题。在merge函数的最后，将temp数组中的元素复制回原数组arr时，使用了相同的索引i来同时访问arr和temp。然而，temp数组是从索引0开始填充的，而arr的目标区间是从left开始的。

错误代码：

for (let i = left; i <= right; i++) {
    arr[i] = temp[i]; // 错误！temp[i]可能越界或取到错误的值
}

当i从left开始时，temp[i]可能会访问到temp数组中未被赋值的区域（如果left > 0），导致undefined。正确做法是使用一个单独的索引来遍历temp数组，或者将temp数组的索引进行偏移。

修正方案：

for (let idx = 0; idx < k; idx++) {
    arr[left + idx] = temp[idx];
}

这里，idx从0开始遍历temp数组，而arr的写入位置通过left + idx进行偏移，确保将temp中的元素正确地放置到arr的相应子区间。

问题点二：初始调用mergesort时right参数的语义不一致

在原始代码中，mergesort(arr, left, right)函数的right参数被期望是子数组的最后一个元素的索引。然而，在初始调用mergesort(arr, 0, n)时，n是数组的长度，这意味着right实际上是数组最后一个元素索引的“后一位”。这种不一致性会导致在处理边界条件时出现问题，例如当right为n时，arr[right]会尝试访问越界元素。

修正方案： 统一right参数的语义。更符合JavaScript等语言习惯的做法是，将right定义为子数组的结束索引（不包含该索引），即左闭右开区间 [left, right)。

问题点三：整数除法的效率问题

计算中间索引mid时使用了parseInt((right - left) / 2) + left。这种方法涉及浮点运算、字符串转换和整数解析，效率较低。

修正方案： 使用位运算符>> 1进行整数除法，这是一种更高效且常用的方法。

let mid = left + ((right - left) >> 1); // 等同于 Math.floor((right - left) / 2) + left

问题点四：merge函数中冗余的元素复制

在merge函数中，有两个for循环用于复制剩余元素：

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

当采用“左闭右开”的right参数语义时，这两个循环的条件会相应改变。实际上，如果right表示不包含的结束索引，并且temp数组在合并过程中只包含合并后的元素，那么在主while循环结束后，i或j中的一个会到达其边界，另一个则指向剩余元素。这些剩余元素可以直接追加到temp中。

优化后的归并排序实现

综合上述分析和修正，以下是采用“左闭右开”区间语义的优化版归并排序实现。这种实现方式在JavaScript中更为常见和推荐。

/**
 * 归并排序主函数
 * @param {Array<number>} arr 待排序数组
 * @param {number} left 子数组的起始索引 (包含)
 * @param {number} right 子数组的结束索引 (不包含)
 */
function mergesort(arr, left, right) {
    // 当子数组长度大于1时才进行排序
    if (right - left > 1) {
        // 计算中间索引，采用位运算提高效率
        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; // 左子数组的当前索引
    let j = mid;  // 右子数组的当前索引
    let k = 0;    // 临时数组的当前索引
    let temp = []; // 临时存储合并结果的数组

    // 比较左右两个子数组的元素，依次放入temp数组
    while (i < mid && j < right) {
        if (arr[i] <= arr[j]) {
            temp[k++] = arr[i++];
        } else {
            temp[k++] = arr[j++];
        }
    }

    // 将左子数组中剩余的元素放入temp
    while (i < mid) {
        temp[k++] = arr[i++];
    }

    // 将右子数组中剩余的元素放入temp
    // 注意：如果left子数组已经全部拷贝完，那么right子数组剩余的元素会直接拷贝。
    // 如果right子数组已经全部拷贝完，那么这个循环不会执行。
    while (j < right) { // 也可以写成 for (; j < right; j++) { temp[k++] = arr[j]; }
        temp[k++] = arr[j++];
    }

    // 将temp数组中的元素拷贝回原数组arr的对应区间
    for (let idx = 0; idx < k; idx++) {
        arr[left + idx] = temp[idx];
    }
}

// 示例用法
let data = [ 5, 3, 7, 2, 9, 12, 4 ];
console.log("原始数组:", data); // 输出: 原始数组: [5, 3, 7, 2, 9, 12, 4]

mergesort(data, 0, data.length); // 初始调用时，right为数组长度
console.log("排序后数组:", data); // 输出: 排序后数组: [2, 3, 4, 5, 7, 9, 12]

let emptyArr = [];
mergesort(emptyArr, 0, emptyArr.length);
console.log("空数组排序后:", emptyArr); // 输出: 空数组排序后: []

let singleArr = [42];
mergesort(singleArr, 0, singleArr.length);
console.log("单元素数组排序后:", singleArr); // 输出: 单元素数组排序后: [42]

总结与注意事项

• 边界条件处理： 在实现递归算法时，对left和right等索引参数的定义（是包含还是不包含）至关重要。统一采用“左闭右开”区间[left, right)是一种推荐的实践，它能简化循环条件和避免越界错误。
• 临时数组回写： merge函数中将临时数组temp的内容复制回原数组arr时，务必确保索引的正确性。temp通常从0开始填充，而arr的目标区间可能从left开始，因此需要进行索引偏移。
• 效率优化： 对于整数除法，使用位运算符>> 1通常比parseInt()或Math.floor()更高效。
• 代码简洁性： 遵循语言习惯，编写逻辑清晰、易于理解的代码。例如，while循环中可以利用k++和i++等后置增量运算符来简化代码。

通过理解和避免这些常见陷阱，开发者可以更自信、更高效地实现归并排序算法。

文中关于的知识介绍，希望对你的学习有所帮助！若是受益匪浅，那就动动鼠标收藏这篇《归并排序陷阱与优化技巧解析》文章吧，也可关注golang学习网公众号了解相关技术文章。