归并排序java代码实现

原创admin 分类：热门问答 2024-05-05 22:47:56 0

归并排序java代码实现
在计算机科学中，排序算法是一类非常重要的算法，它们负责将一系列的元素按照特定顺序进行排列。在众多的排序算法中，归并排序以其稳定性和效率而著称。作为一名软件开发者，我经常在处理大数据集时使用归并排序，因为它在最坏情况下也能保持较好的性能。归并排序是由约翰·冯·诺伊曼在1945年提出的，它是一种分治算法，通过将数据集分成更小的集合，然后对这些集合进行排序，最后将排序后的集合合并起来，从而实现整个数据集的排序。归并排序的效率通常比插入排序和选择排序等简单算法要高，尤其是在数据量大的情况下。

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

归并排序和快速排序都是分治算法，但它们在实现细节上有所不同。快速排序通过选择一个“基准”值，然后将数据分为两部分，一部分数据比基准值小，另一部分数据比基准值大，接着对这两部分数据分别进行快速排序操作。而归并排序则是将数据集不断地分成两半，直到每一半只有一个元素，后开始合并这些元素，直到整个数据集被排序。

特性	归并排序	快速排序
稳定性	稳定	不稳定
时间复杂度	最坏O(n log n)	平均O(n log n)，最坏O(n^2)
空间复杂度	O(n)	O(log n)
递归	需要	需要

核心类与方法

归并排序的核心在于两个主要的方法：merge()和mergeSort()。mergeSort()方法用于递归地将数组分成两半，直到每一半只有一个元素，然后调用merge()方法将这些元素合并并排序。

使用场景

归并排序由于其稳定性和在大数据集上的良好性能，非常适合用于以下场景：

大数据集的排序。
需要稳定排序结果的场合。
在线排序，即数据逐渐增加，需要不断排序的情况。

代码案例

以下是归并排序的Java代码实现：

public class MergeSort {
    public static void main(String[] args) {
        int[] array = {12, 11, 13, 5, 6, 7};
        mergeSort(array, 0, array.length - 1);
        for (int i : array) {
            System.out.print(i + " ");
        }
    }

    public static void mergeSort(int[] array, int left, int right) {
        if (left < right) {
            int middle = (left + right) / 2;
            mergeSort(array, left, middle);
            mergeSort(array, middle + 1, right);
            merge(array, left, middle, right);
        }
    }

    public static void merge(int[] array, int left, int middle, int right) {
        int length1 = middle - left + 1;
        int length2 = right - middle;
        int[] leftArray = new int[length1];
        int[] rightArray = new int[length2];
        for (int i = 0; i < length1; i++) {
            leftArray[i] = array[left + i];
        }
        for (int j = 0; j < length2; j++) {
            rightArray[j] = array[middle + 1 + j];
        }
        int i = 0, j = 0;
        int k = left;
        while (i < length1 && j < length2) {
            if (leftArray[i] <= rightArray[j]) {
                array[k] = leftArray[i];
                i++;
            } else {
                array[k] = rightArray[j];
                j++;
            }
            k++;
        }
        while (i < length1) {
            array[k] = leftArray[i];
            i++;
            k++;
        }
        while (j < length2) {
            array[k] = rightArray[j];
            j++;
            k++;
        }
    }
}

补充知识

使用表格来补充归并排序的一些相关知识：

术语	描述
分治法	一种算法策略，将问题分解成多个小问题，解决小问题后再合并解决大问题。
稳定性	排序算法中，如果相等的元素在排序后保持原有的相对顺序，则称该算法是稳定的。
时间复杂度	算法执行所需时间与输入规模之间的关系。
空间复杂度	算法执行过程中所需的存储空间与输入规模之间的关系。