Java数据结构与算法:排序算法之归并排序

发布时间:2024年01月19日

Java数据结构与算法:排序算法之归并排序

大家好,我是免费搭建查券返利机器人赚佣金就用微赚淘客系统3.0的小编,寒冬来袭,虽然冷空气刺骨,但我们程序猿依然保持风度。今天,我们将深入研究Java中一种高效且稳定的排序算法——归并排序。这种分而治之的排序策略让我们一同领略排序的艺术。

归并排序简介

归并排序是一种基于分治思想的排序算法,它将待排序的序列划分成若干个子序列,分别进行排序,最后再合并成一个有序的序列。这一过程通过递归实现,直到每个子序列中只有一个元素,即可认为其已经有序。随后,通过两两合并有序序列,最终完成整个序列的排序。

归并排序的基本步骤

  1. 初始状态: 将待排序序列划分为若干个子序列。

  2. 递归排序: 对每个子序列进行递归排序,直到每个子序列只包含一个元素。

  3. 合并序列: 将两个有序的子序列合并成一个有序的序列,重复该过程直到整个序列有序。

归并排序Java实现

下面是一个简单的Java代码示例,演示了如何使用归并排序对一个整型数组进行升序排序:

public class MergeSort {
    public static void main(String[] args) {
        int[] array = {64, 34, 25, 12, 22, 11, 90};

        // 打印排序前的数组
        System.out.println("排序前的数组:" + Arrays.toString(array));

        // 执行归并排序
        mergeSort(array, 0, array.length - 1);

        // 打印排序后的数组
        System.out.println("排序后的数组:" + Arrays.toString(array));
    }

    // 归并排序算法实现
    static void mergeSort(int[] arr, int left, int right) {
        if (left < right) {
            // 计算中间位置
            int middle = (left + right) / 2;

            // 对左右两部分分别进行归并排序
            mergeSort(arr, left, middle);
            mergeSort(arr, middle + 1, right);

            // 合并排序结果
            merge(arr, left, middle, right);
        }
    }

    // 合并两个有序序列
    static void merge(int[] arr, int left, int middle, int right) {
        // 计算左右两部分的长度
        int n1 = middle - left + 1;
        int n2 = right - middle;

        // 创建临时数组存储左右两部分的元素
        int[] leftArray = new int[n1];
        int[] rightArray = new int[n2];

        // 将元素复制到临时数组
        for (int i = 0; i < n1; ++i)
            leftArray[i] = arr[left + i];
        for (int j = 0; j < n2; ++j)
            rightArray[j] = arr[middle + 1 + j];

        // 初始化左右两部分数组的下标
        int i = 0, j = 0;

        // 初始化合并后的数组下标
        int k = left;

        // 合并左右两部分的元素
        while (i < n1 && j < n2) {
            if (leftArray[i] <= rightArray[j]) {
                arr[k] = leftArray[i];
                i++;
            } else {
                arr[k] = rightArray[j];
                j++;
            }
            k++;
        }

        // 将左右两部分剩余的元素复制到合并后的数组
        while (i < n1) {
            arr[k] = leftArray[i];
            i++;
            k++;
        }

        while (j < n2) {
            arr[k] = rightArray[j];
            j++;
            k++;
        }
    }
}

归并排序的时间复杂度

归并排序的时间复杂度为O(n logn),其中n是待排序序列的长度。尽管归并排序在时间复杂度上相对较高,但它具有稳定性和适应性,适用于各种数据情况。

通过这篇文章,相信你对归并排序有了更深入的理解。在接下来的系列中,我们将一起学习更多Java中的排序算法,为你呈现更多有趣的内容。敬请期待!

文章来源:https://blog.csdn.net/weixin_44627014/article/details/135630793
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。