归并排序常见错误与优化方法

哈喽！今天心血来潮给大家带来了《归并排序实现常见错误与优化技巧》，想必大家应该对文章都不陌生吧，那么阅读本文就都不会很困难，以下内容主要涉及到，若是你正在学习文章，千万别错过这篇文章~希望能帮助到你！

本文深入探讨了JavaScript归并排序实现中常见的索引处理错误、边界条件问题以及性能优化点。通过分析一个典型的错误代码示例，文章详细解释了在`merge`函数中将临时数组数据复制回原数组时的索引错位、不当的中间索引计算方式，以及数组右边界参数定义不一致的问题。最终，提供了一个遵循“左闭右开”区间原则且经过优化的归并排序实现，旨在帮助开发者构建更健壮、高效的排序算法。

归并排序概述

归并排序（Merge Sort）是一种基于分治思想的高效稳定排序算法。其基本思想是将一个大的无序数组递归地分成两个较小的子数组，直到子数组只包含一个元素（自然有序），然后将这些有序的子数组两两合并，最终得到一个完全有序的数组。这个过程的核心在于merge（合并）操作，它负责将两个已排序的子数组合并成一个更大的有序数组。

初始问题代码分析

我们首先来看一个常见的归并排序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++) { // 错误点1
        arr[i] = temp[i]; // 错误点1
    }
}

let arr = [ 5, 3, 7, 2, 9, 12, 4 ];
n = arr.length;
mergesort(arr, 0, n); // 错误点2

这段代码在执行后，可能会输出类似 [undefined, undefined, undefined, undefined, undefined, undefined, 3, 5] 的结果，表明排序未能正确完成，并且数组中出现了undefined值。这通常是由于索引越界或数据未正确复制导致的。

错误识别与修正

通过仔细分析，我们可以发现上述代码中存在以下几个关键问题：

1. merge函数中数据回写错误

问题描述： 在merge函数的最后一步，将临时数组temp中的数据复制回原数组arr时，使用了相同的索引i来访问arr和temp。

// 原始错误代码片段
for (let i = left; i <= right; i++) {
    arr[i] = temp[i];
}

temp数组是从索引0开始填充的，其有效元素范围是[0, k-1]。而arr数组的目标复制范围是从left到right。直接使用i作为temp的索引会导致temp[i]在i > k-1时访问到undefined，或者在left不为0时，temp[left]可能访问到错误的数据。

修正方案： 需要使用两个不同的索引变量，一个用于遍历temp数组（从0开始），另一个用于确定在arr数组中的起始位置（从left开始）。

// 修正后的代码片段
for (let idx = 0; idx < k; idx++) {
    arr[left + idx] = temp[idx];
}

2. 初始调用中的右边界参数

问题描述： 初始调用mergesort(arr, 0, n)时，将n（即arr.length）作为right参数传递。然而，mergesort函数内部的right参数被期望为数组的最后一个元素的索引，即n-1。这种不一致的语义会导致right参数超出实际数组范围。

修正方案： 如果我们坚持right为最后一个元素的索引的语义，那么初始调用应为mergesort(arr, 0, n - 1)。然而，更推荐的做法是采用“左闭右开”的区间语义，这将在后续的优化实践中详细说明。

3. 中间索引mid的计算方式

问题描述： let mid = parseInt((right - left) / 2) + left; 这种计算mid的方式虽然在大多数情况下能得到正确结果，但parseInt操作涉及到字符串转换，效率较低。

优化方案： 在JavaScript中，更高效且推荐的整数除法方式是使用位运算符>> 1（右移一位，相当于除以2并向下取整）。

// 优化后的mid计算
let mid = left + ((right - left) >> 1);

4. merge函数中剩余元素的复制

问题描述： 原始merge函数在主while循环结束后，有两段for循环用于复制剩余元素：

// 原始代码片段
for (; i <= mid; i++) {
    temp[k] = arr[i];
    k++;
}
for (; j <= right; j++) {
    temp[k] = arr[j];
    k++;
}

这些循环将arr中未处理的元素复制到temp中。虽然功能上正确，但当采用“左闭右开”的区间语义并优化merge逻辑后，这部分可以更简洁地表达。

优化实践：采用“左闭右开”区间语义

在许多编程语言和算法实现中，数组/区间操作常采用“左闭右开”的区间表示法，即[left, right)，表示从left索引开始（包含）到right索引结束（不包含）。这种约定可以简化边界条件的处理，尤其是在递归和循环中。

下面是基于“左闭右开”语义的优化版归并排序实现：

/**
 * 归并排序主函数
 * @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 (如果有的话)
    // 注意：如果左半部分有剩余，右半部分不可能有；反之亦然。
    // 所以这里的两个while循环只会执行其中一个。
    while (j < right) {
        temp[k++] = arr[j++];
    }

    // 将temp数组中的有序元素复制回原数组的对应位置
    // 这里的i重新用作temp数组的索引，从0开始
    for (let idx = 0; idx < k; idx++) {
        arr[left + idx] = temp[idx];
    }
}

// 示例调用
let data = [ 5, 3, 7, 2, 9, 12, 4 ];
mergesort(data, 0, data.length); // 初始调用：从索引0到数组长度(不包含)
console.log(data); // 输出: [2, 3, 4, 5, 7, 9, 12]

优化版代码的特点：

1. “左闭右开”区间语义： mergesort(arr, left, right) 和 merge(arr, left, mid, right) 中的 right 参数都表示子数组结束位置的下一个索引，不包含该索引处的元素。这使得right - left可以直接表示子数组的长度。
2. mid计算优化： 使用 left + ((right - left) >> 1) 替代 parseInt，提高了效率。
3. mergesort递归调用： 调整为 mergesort(arr, left, mid) 和 mergesort(arr, mid, right)，与“左闭右开”语义保持一致。
4. merge函数简化：
   • while (i < mid && j < right)：循环条件精确反映了左右子数组的有效范围。
   • while (i < mid) 和 while (j < right)：这两个循环用于处理某个子数组可能提前遍历完的情况，将另一个子数组中剩余的元素直接复制到temp。由于两个子数组本身已经有序，直接复制即可。
   • for (let idx = 0; idx < k; idx++) { arr[left + idx] = temp[idx]; }：修正了数据回写时的索引问题，确保temp中的元素正确地复制回arr的指定位置。
5. 初始调用： mergesort(data, 0, data.length)，直接使用arr.length作为右边界，符合“左闭右开”语义。

总结与注意事项

实现归并排序时，以下几点是需要特别注意的：

• 索引管理： 这是归并排序中最容易出错的地方。务必清晰定义每个参数（left, mid, right）的含义（是包含还是不包含），并在整个函数中保持一致。推荐使用“左闭右开”区间[left, right)，它能简化很多边界条件判断。
• mid计算： 使用位运算>> 1进行整数除法，避免parseInt带来的性能开销。
• merge逻辑： 确保merge函数能够正确地将两个已排序的子数组合并成一个，并且最终将合并结果准确无误地复制回原数组的正确位置。特别是从临时数组回写数据时，要处理好索引的偏移。
• 空间复杂度： 归并排序通常需要额外的O(N)空间来存储临时数组temp。在某些场景下，如果内存是严格限制的，可能需要考虑原地归并排序等更复杂的变体，但实现难度会大大增加。

通过理解和应用这些修正与优化实践，开发者可以构建出健壮、高效且符合行业最佳实践的JavaScript归并排序实现。

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