Java 排序算法之归并排序

算法简介

归并排序（Merge Sort）是一种基于分治思想的排序算法，其基本思想是将待排序的序列不断列表分割为子序列，直到每个子序列只有一个元素，然后将子序列两两合并并按照考虑的比较规则合并成一个有序的大序列，直到最后整个序列有序。

归并排序的时间复杂度为O(nlogn)，稳定排序，但是需要额外的空间复杂度O(n)，因为需要额外的空间用于合并序列。

示例说明

下面我们使用两个示例来演示归并排序的具体实现过程。

示例一

对于一个包含6个元素（4, 7, 3, 1, 9, 2）待排序的数组，下面是归并排序的具体实现过程。

1. 将序列分割为两个子序列（4, 7, 3）和（1, 9, 2）。
2. 对于每个子序列递归调用归并排序，得到两个有序的子序列（3, 4, 7）和（1, 2, 9）。
3. 合并两个有序子序列，得到最终有序序列（1, 2, 3, 4, 7, 9）。

示例二

对于一个包含8个元素（5, 8, 6, 3, 9, 2, 1, 7）待排序的数组，下面是归并排序的具体实现过程。

1. 将序列分割为两个子序列（5, 8, 6, 3）和（9, 2, 1, 7）。
2. 将子序列（5, 8, 6, 3）分割为两个子序列（5, 8）和（6, 3）。
3. 对于每个子序列递归调用归并排序，得到两个有序的子序列（5, 8）和（3, 6）。
4. 合并两个有序子序列，得到有序子序列（3, 5, 6, 8）。
5. 将子序列（9, 2, 1, 7）分割为两个子序列（9, 2）和（1, 7）。
6. 对于每个子序列递归调用归并排序，得到两个有序的子序列（2, 9）和（1, 7）。
7. 合并两个有序子序列，得到有序子序列（1, 2, 7, 9）。
8. 合并两个有序子序列（3, 5, 6, 8）和（1, 2, 7, 9），得到最终有序序列（1, 2, 3, 5, 6, 7, 8, 9）。

Java 代码实现

下面给出 Java 语言实现归并排序算法的代码。

public class MergeSort {
    public static void merge(int[] arr, int start, int mid, int end) {
        int[] tmpArr = new int[end - start + 1];
        int i = start;
        int j = mid + 1;
        int k = 0;
        while(i <= mid && j <= end) {
            if(arr[i] <= arr[j])
                tmpArr[k++] = arr[i++];
            else
                tmpArr[k++] = arr[j++];
        }
        while(i <= mid)
            tmpArr[k++] = arr[i++];
        while(j <= end)
            tmpArr[k++] = arr[j++];
        for(i = 0, k = start; k <= end; i++, k++) {
            arr[k] = tmpArr[i];
        }
    }

    public static void mergeSort(int[] arr, int start, int end) {
        if(start >= end)
            return;
        int mid = start + (end - start) / 2;
        mergeSort(arr, start, mid);
        mergeSort(arr, mid+1, end);
        merge(arr, start, mid, end);
    }

    public static void main(String[] args) {
        int[] arr = new int[] {5,8,6,3,9,2,1,7};
        mergeSort(arr, 0, arr.length - 1);
        for(int i : arr)
            System.out.print(i + " ");
    }
}

在上述代码中，merge函数用于合并两个有序子序列（start，mid）和（mid + 1，end），递归调用mergeSort函数将数组分割至只有一个元素再合并，最终得到排序数组。