归并排序算法-java教程-PHP中文网

归并排序算法

聖光之護

发布： 2025-01-21 23:52:11

原创

429人浏览过

归并排序算法详解

归并排序算法

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

图解归并排序

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

归并排序算法

将其分成两个子数组：

归并排序算法

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

归并排序算法

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

网梦购物系统

一套功能完善、性能稳定的经典网上购物系统，掌握了一整套从算法，数据结构到产品安全性方面的领先技术，使程序无论在安全性、负载能力方面均获得了成功，新版购物系统集成多种在线支付方式，全后台操作管理，并集成了Ewebedit编辑器，即使只有电脑基础知识的人也能够轻松操作和管理部分新增功能：集成多种网上支付形式，后台灵活切换增加Ewebedit编辑器，添加信息更容易！简洁、明快、新颖的界面，给人以美的感觉

查看详情

归并排序算法

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

归并排序算法

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()高效地复制数组，并简化了合并过程中的比较和赋值逻辑，提高了代码的可读性和效率。

祝您学习愉快！

以上就是归并排序算法的详细内容，更多请关注php中文网其它相关文章！