归并算法之有序数组合并算法实现

下面是“归并算法之有序数组合并算法实现”的完整攻略。

什么是归并算法？

归并排序（Merge Sort）是一种基于归并操作的排序算法。将一个数组拆分成两个数组，对每个子数组分别进行排序，最后将排序好的两个子数组合并成一个有序的数组。

有序数组合并算法的实现

基本思路：

• 先比较两个数组的第一个元素，将较小的元素放入结果数组
• 然后继续比较较小元素所在数组的下一个元素和另一个数组的当前元素，将较小的元素放入结果数组
• 再将较小元素所在数组的下一个元素和另一个数组的当前元素进行比较，以此类推，直到一个数组的元素全部都存入结果数组

具体步骤：

1. 新建一个长度为两个数组长度和的结果数组
   let result = new Array(arr1.length + arr2.length);

2. 用两个指针分别指向两个数组的第一个元素，并将较小的元素放入结果数组。
   let i = 0;
let j = 0;
let k = 0; // 结果数组下标
while (i < arr1.length && j < arr2.length) {
if (arr1[i] < arr2[j]) {
result[k++] = arr1[i++];
} else {
result[k++] = arr2[j++];
}
}

3. 将剩余的元素全部存入结果数组中。
   while (i < arr1.length) {
result[k++] = arr1[i++];
}
while (j < arr2.length) {
result[k++] = arr2[j++];
}

完整代码示例：

function mergeSortedArrays(arr1, arr2) {
    let result = new Array(arr1.length + arr2.length);
    let i = 0;
    let j = 0;
    let k = 0; // 结果数组下标
    while (i < arr1.length && j < arr2.length) {
        if (arr1[i] < arr2[j]) {
            result[k++] = arr1[i++];
        } else {
            result[k++] = arr2[j++];
        }
    }
    while (i < arr1.length) {
        result[k++] = arr1[i++];
    }
    while (j < arr2.length) {
        result[k++] = arr2[j++];
    }
    return result;
}

示例说明

示例1

输入：

let arr1 = [1, 3, 5, 7];
let arr2 = [2, 4, 6, 8, 10];
console.log(mergeSortedArrays(arr1, arr2)); 

输出：

[1, 2, 3, 4, 5, 6, 7, 8, 10]

示例2

输入：

let arr1 = [2, 4, 6];
let arr2 = [1, 3, 5, 7, 8, 9];
console.log(mergeSortedArrays(arr1, arr2)); 

输出：

[1, 2, 3, 4, 5, 6, 7, 8, 9]

以上是“归并算法之有序数组合并算法实现”的完整攻略，如果您还有疑问请随时向我提问。

阅读剩余 54%