Java 中归并排序算法详解

算法介绍

归并排序是一种稳定的分治算法，时间复杂度为 O(nlogn)，相较于快速排序，归并排序对于需要稳定排序的数据更加适用。

算法步骤

归并排序的主要思想是分治，即将一个大的问题分解为若干个小问题，解决每个小问题，然后合并得到最终的解决方案。

归并排序的具体步骤如下：

1. 分解：将待排序的数组分解为若干个小数组，直到每个小数组仅包含一个元素，即认为每个小数组本身有序。
2. 归并：将小数组两两合并，形成更大的有序数组。重复该步骤，直到所有的小数组合并成一个大的有序数组。

实现示例

以下为 Java 实现归并排序算法的示例代码：

public class MergeSort {
    private void merge(int[] arr, int left, int mid, int right) {
        int[] temp = new int[right - left + 1];
        int i = left, j = mid + 1, k = 0;
        while (i <= mid && j <= right) {
            if (arr[i] < arr[j]) {
                temp[k] = arr[i];
                k++;
                i++;
            } else {
                temp[k] = arr[j];
                k++;
                j++;
            }
        }
        while (i <= mid) {
            temp[k] = arr[i];
            k++;
            i++;
        }
        while (j <= right) {
            temp[k] = arr[j];
            k++;
            j++;
        }
        for (int p = 0; p < temp.length; p++) {
            arr[left + p] = temp[p];
        }
    }

    private void mergeSort(int[] arr, int left, int right) {
        if (left >= right) {
            return;
        }
        int mid = left + (right - left) / 2;
        mergeSort(arr, left, mid);
        mergeSort(arr, mid + 1, right);
        merge(arr, left, mid, right);
    }

    public void sort(int[] arr) {
        if (arr == null || arr.length == 0) {
            return;
        }
        mergeSort(arr, 0, arr.length - 1);
    }
}

其中，merge 方法实现数组的合并，mergeSort 方法实现递归分解数组及合并有序数组，sort 方法对外暴露调用接口，调用时需要传入待排序的数组。

以下为使用示例：

public static void main(String[] args) {
    int[] arr = {5, 3, 7, 2, 8, 4, 1, 6};
    MergeSort mergeSort = new MergeSort();
    mergeSort.sort(arr);
    System.out.println(Arrays.toString(arr));
}

输出结果为：

[1, 2, 3, 4, 5, 6, 7, 8]

另外一个示例是将一个字符串数组按照字典序排序：

public static void main(String[] args) {
    String[] arr = {"hello", "world", "java", "merge", "sort"};
    MergeSort mergeSort = new MergeSort();
    mergeSort.sort(arr);
    System.out.println(Arrays.toString(arr));
}

输出结果为：

[java, hello, merge, sort, world]

总结

归并排序是一种常用的排序算法，稳定而快速。本文详细讲解了该算法的实现细节和示例代码。