归并排序算法

wufei123 2025-01-26 阅读:1 评论:0

归并排序算法详解归并排序的核心思想是分治：将数组不断分割成更小的子数组，直到每个子数组只包含一个元素（此时已排序），然后逐步合并这些子数组，在合并过程中完成排序。排序发生在合并阶段，而非分割阶段。图解归并排序首先，我们有一个待排序的...

归并排序算法详解

归并排序算法

归并排序的核心思想是分治：将数组不断分割成更小的子数组，直到每个子数组只包含一个元素（此时已排序），然后逐步合并这些子数组，在合并过程中完成排序。排序发生在合并阶段，而非分割阶段。

图解归并排序

首先，我们有一个待排序的数组：

归并排序算法

将其分成两个子数组：

归并排序算法

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

归并排序算法

接下来是合并和排序阶段，每次合并两个已排序的子数组，得到一个新的已排序的数组：

归并排序算法

最终得到完全排序的数组：

归并排序算法

Java代码实现及优化

初始代码存在效率问题，主要体现在数组元素的复制和合并逻辑上。以下提供优化后的代码：

import java.util.Arrays;

public static void mergeSort(int[] array) {
    int n = array.length;
    if (n < 2) {
        return; // 数组长度小于2，无需排序
    }

    int middle = n / 2;
    int[] left = Arrays.copyOfRange(array, 0, middle);
    int[] right = Arrays.copyOfRange(array, middle, n);

    mergeSort(left);
    mergeSort(right);

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

    while (i < left.length) {
        array[k++] = left[i++];
    }

    while (j < right.length) {
        array[k++] = right[j++];
    }
}

此优化版本使用Arrays.copyOfRange()高效地复制数组，并简化了合并过程中的比较和赋值逻辑，提高了代码的可读性和效率。

祝您学习愉快！

以上就是归并排序算法的详细内容，更多请关注知识资源分享宝库其它相关文章！