java归并排序算法代码

原创admin 分类：热门问答 2024-05-05 19:13:52 0

java归并排序算法代码
在编程的世界里，排序算法是处理数据集的基石。作为一名程序员，我经常需要对数据进行排序，以便于分析和处理。归并排序（Merge Sort）作为一种高效的排序算法，以其稳定性和分治策略在众多算法中脱颖而出。归并排序的基本思想是将一个大问题分解成若干个较小的子问题，递归地解决这些子问题，然后将这些子问题的解合并起来，得到原问题的解。

定义与目的

归并排序是一种分治算法，它的主要目的是对一个给定的数组或者列表进行排序。它通过递归地将数组分成两半，直到每个子数组只有一个元素，然后通过合并这些有序的子数组来构建一个有序的数组。

归并排序与快速排序的对比

尽管归并排序和快速排序都是分治算法，但它们在实现和性能上有所不同。以下是两者的对比表格：

特性	归并排序	快速排序
时间复杂度	最坏情况 (O(n \log n))	平均情况 (O(n \log n)), 最坏 (O(n^2))
空间复杂度	(O(n))	(O(\log n))
稳定性	稳定	不稳定
递归	需要	需要
使用场景	对于大数据集更优	对于小数据集或基本有序的数据集更优

核心类与方法

归并排序的核心在于两个主要的操作：分割（Divide）和合并（Merge）。分割操作是递归地将数组分成两半，直到每个子数组只包含一个元素。合并操作则是将两个已经排序的子数组合并成一个有序数组。

使用场景

归并排序由于其稳定性，非常适合于那些需要保持相等元素相对顺序的场景。此外，归并排序在处理大数据集时，由于其时间复杂度为 (O(n \log n))，通常比快速排序有更好的性能表现。

代码案例

以下是两个归并排序的代码案例：

案例一：

public class MergeSortExample1 {
    public static void mergeSort(int[] arr) {
        if (arr.length < 2) {
            return;
        }
        int mid = arr.length / 2;
        int[] left = new int[mid];
        int[] right = new int[arr.length - mid];

        System.arraycopy(arr, 0, left, 0, mid);
        System.arraycopy(arr, mid, right, 0, arr.length - mid);

        mergeSort(left);
        mergeSort(right);
        merge(left, right, arr);
    }

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

    public static void main(String[] args) {
        int[] array = {3, 1, 4, 1, 5, 9, 2};
        mergeSort(array);
        System.out.println("Sorted array: " + Arrays.toString(array));
    }
}

案例二：

public class MergeSortExample2 {
    public static void mergeSort(int[] arr, int[] temp, int left, int right) {
        if (left < right) {
            int mid = (left + right) / 2;
            mergeSort(arr, temp, left, mid);
            mergeSort(arr, temp, mid + 1, right);
            merge(arr, temp, left, mid, right);
        }
    }

    private static void merge(int[] arr, int[] temp, int left, int mid, int right) {
        System.arraycopy(arr, left, temp, left, right - left + 1);
        int i = left;
        int j = mid + 1;
        int k = left;

        while (i <= mid && j <= right) {
            if (temp[i] <= temp[j]) {
                arr[k++] = temp[i++];
            } else {
                arr[k++] = temp[j++];
            }
        }
        while (i <= mid) {
            arr[k++] = temp[i++];
        }
    }

    public static void main(String[] args) {
        int[] array = {3, 1, 4, 1, 5, 9, 2};
        int[] temp = new int[array.length];
        mergeSort(array, temp, 0, array.length - 1);
        System.out.println("Sorted array: " + Arrays.toString(array));
    }
}

知识点	描述
分治法	将复杂问题分解成若干个规模较小的相同问题
递归	一种在程序中调用自身的方法
稳定性	排序算法中，相等元素的相对顺序保持不变
时间复杂度	描述算法执行时间随输入规模增长的变化
空间复杂度	描述算法执行过程中所需的存储空间大小
递归工作空间	递归调用所需的额外存储空间