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

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中的排序算法，为你呈现更多有趣的内容。敬请期待！