归并排序算法

深入了解归并排序算法

归并排序算法的核心思想是分治法，即“分而治之”。它将一个数组递归地划分为更小的子数组，直到每个子数组只包含一个元素（此时已排序）。然后，它将这些子数组合并成更大的已排序数组。值得注意的是，排序过程发生在合并阶段，而不是在分割阶段。

算法演示

假设我们有一个待排序的数组：

我们将数组分成左右两个子数组：

继续递归分割，直到每个子数组都只有一个元素：

接下来，合并并排序这些子数组：较小的值放在左边，较大的值放在右边。

最终完成排序：

代码实现 (Java)

最初的Java代码存在一些效率问题，我们可以对其进行优化。改进后的代码如下：

import java.util.Arrays;

public static void mergeSort(int[] array) {
    int n = array.length;
    if (n < 2) {
        return;
    }
    int middle = n / 2;
    int[] left = Arrays.copyOfRange(array, 0, middle);
    int[] right = Arrays.copyOfRange(array, middle, n);

    mergeSort(left);
    mergeSort(right);

    int leftIndex = 0;
    int rightIndex = 0;
    int arrayIndex = 0;

    while (leftIndex < left.length || rightIndex < right.length) {
        if (leftIndex < left.length && (rightIndex >= right.length || left[leftIndex] <= right[rightIndex])) {
            array[arrayIndex++] = left[leftIndex++];
        } else {
            array[arrayIndex++] = right[rightIndex++];
        }
    }
}

这段优化后的代码使用了Arrays.copyOfRange()方法来更高效地复制数组元素，并简化了合并过程中的循环条件和判断语句，从而提高了代码的可读性和效率。

希望这段改进后的解释和代码能帮助你更好地理解归并排序算法！

以上是归并排序算法的详细内容。更多信息请关注PHP中文网其他相关文章！