如何在 Java 的归并排序算法中合并两个已排序的子数组

简介

本教程将指导你使用 Java 编程语言在归并排序算法中合并两个已排序子数组的过程。归并排序是一种流行且高效的分治算法，用于对大型数据集进行排序。理解合并过程对于在 Java 应用程序中有效地实现归并排序算法至关重要。

Skills Graph

理解归并排序算法

归并排序是一种流行且高效的排序算法，遵循分治范式。它的工作方式是将输入数组递归地划分为更小的子数组，对它们进行排序，然后将已排序的子数组合并回一起，形成最终的已排序数组。

归并排序算法的关键步骤如下：

划分

1. 将输入数组分成两半，直到得到单个元素的子数组。

征服

2. 通过比较子数组的元素并合并它们来对子数组进行排序。

合并

3. 将已排序的子数组合并回一起，形成最终的已排序数组。

归并排序的时间复杂度为 O(n log n)，这使其成为对大型数据集进行排序的有效选择。在输入数组太大而无法放入内存的情况下，它特别有用，因为可以使用外部存储或分布式计算来有效地实现它。

public static void mergeSort(int[] arr) {
    if (arr.length > 1) {
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);

        mergeSort(left);
        mergeSort(right);

        merge(arr, left, right);
    }
}

private static void merge(int[] arr, int[] left, int[] right) {
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }
    while (i < left.length) {
        arr[k++] = left[i++];
    }
    while (j < right.length) {
        arr[k++] = right[j++];
    }
}

上述代码展示了归并排序算法在 Java 中的实现。mergeSort 方法递归地将输入数组划分为更小的子数组，而 merge 方法将已排序的子数组合并回一起，形成最终的已排序数组。

归并排序中合并已排序子数组

归并排序算法的关键步骤是合并已排序的子数组。此过程涉及将两个或多个已排序的子数组合并成一个单一的已排序数组。

合并操作

合并操作通过比较已排序子数组的元素并将它们按正确顺序放入最终数组中来执行。一般步骤如下：

1. 初始化三个指针：一个用于左子数组，一个用于右子数组，一个用于合并后的数组。
2. 比较左子数组和右子数组当前位置的元素。
3. 将较小的元素添加到合并后的数组中，并将相应的指针向前移动。
4. 重复步骤2和3，直到其中一个子数组用尽。
5. 将非空子数组中剩余的元素添加到合并后的数组中。

以下是Java中合并操作的示例实现：

private static void merge(int[] arr, int[] left, int[] right) {
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }
    while (i < left.length) {
        arr[k++] = left[i++];
    }
    while (j < right.length) {
        arr[k++] = right[j++];
    }
}

此实现将两个已排序的子数组left和right合并到原始数组arr中。

合并操作的可视化

合并操作可以使用如下所示的图表进行可视化：

在此图表中，左子数组和右子数组合并到最终的已排序数组中。

通过理解合并操作，你可以在Java中有效地实现归并排序算法并高效地对数组进行排序。

在Java中实现归并排序

既然我们已经对归并排序算法和合并操作有了扎实的理解，那就让我们深入探讨一下如何在Java中实现归并排序。

归并排序算法实现

归并排序算法可以通过以下步骤在Java中实现：

1. 定义一个接受输入数组的mergeSort方法。
2. 如果数组元素多于一个，将其分成两半。
3. 对左半部分和右半部分递归调用mergeSort方法。
4. 使用merge方法合并已排序的左半部分和右半部分。

以下是实现归并排序算法的Java代码：

public static void mergeSort(int[] arr) {
    if (arr.length > 1) {
        int mid = arr.length / 2;
        int[] left = Arrays.copyOfRange(arr, 0, mid);
        int[] right = Arrays.copyOfRange(arr, mid, arr.length);

        mergeSort(left);
        mergeSort(right);

        merge(arr, left, right);
    }
}

private static void merge(int[] arr, int[] left, int[] right) {
    int i = 0, j = 0, k = 0;
    while (i < left.length && j < right.length) {
        if (left[i] <= right[j]) {
            arr[k++] = left[i++];
        } else {
            arr[k++] = right[j++];
        }
    }
    while (i < left.length) {
        arr[k++] = left[i++];
    }
    while (j < right.length) {
        arr[k++] = right[j++];
    }
}

让我们来分析一下这段代码：

1. mergeSort方法接受一个输入数组arr。
2. 如果数组元素多于一个，使用mid变量将其分成两半。
3. 使用Arrays.copyOfRange创建left和right子数组。
4. 对left和right子数组递归调用mergeSort方法。
5. 调用merge方法将已排序的left和right子数组合并回原始的arr中。

merge方法负责通过比较两个已排序子数组的元素，并将它们按正确顺序放入最终数组中来合并这两个子数组。

时间复杂度

归并排序算法的时间复杂度为O(n log n)，这使得它成为对大型数据集进行排序的有效选择。归并排序中使用的分治方法确保了该算法能够随着输入大小的增加而良好地扩展。

通过理解Java中归并排序的实现，你可以有效地使用此算法对数组进行排序，并解决各种与排序相关的问题。

总结

在本Java教程中，你已经学习了如何在归并排序算法中高效地合并两个已排序的子数组。通过理解逐步过程并在Java中实现合并操作，你可以有效地应用归并排序算法对大型数据集进行排序，并提高Java应用程序的性能。