排序算法（七）归并排序

归并排序分两个阶段：

• 第一阶段：分组，假设集合一共有n个元素，算法将会对集合进行逐层的折半分组，一直到每组只有一个元素为止；
• 第二阶段：归并，每个小组内部比较出先后顺序后，小组之间会展开进一步的比较和排序进而合并成一个大足，大组间继续比较和排序并合并成更大的组，反复执行最终所有元素合并成一个有序的集合。
  归并包含三步：
  • 第一步，创建一个长度为两个小集合长度之和的大集合用于存储归并结果；
  • 第二步，从左到右逐一比较两个小集合中的元素，把较小的元素优先放入大集合 ；
  • 第三步，从另一个还有剩余元素的集合中，把剩余元素按顺序复制到大集合尾部。

复杂度分析

时间复杂度：O(nlogn)
空间复杂度：O(n)

Java 代码实现

import java.util.Arrays;

public class MergeSort {

    public static void sort(int[] data, int start, int end) {
        if (start < end) {
            int middle = (start + end) / 2;
            sort(data, start, middle);
            sort(data, middle + 1, end);
            merge(data, start, middle, end);
        }
    }
    
    private static void merge(int[] data, int start, int middle, int end) {
        int[] temp = new int[end - start + 1];
        int p1 = start;
        int p2 = middle + 1;
        int p = 0;
        while (p1 <= middle && p2 <= end) {
            if (data[p1] <= data[p2]) {
                temp[p] = data[p1++];
            } else {
                temp[p] = data[p2++];
            }
            p++;
        }
        while (p1 <= middle) {
            temp[p++] = data[p1++];
        }
        while (p2 <= end) {
            temp[p++] = data[p2++];
        }
        for (int i = 0; i < temp.length; i++) {
            data[i + start] = temp[i];
        }
    }

    public static void main(String[] args) {
        int[] data = {34, 24, 93, 1, 32, 98, 18, 39};
        sort(data, 0, data.length - 1);
        System.out.println(Arrays.toString(data));
    }
}

运行结果

[1, 18, 24, 32, 34, 39, 93, 98]