归并排序 (Merge Sort) 算法详解

归并排序 (Merge Sort) 是建立在归并操作上的一种有效的排序算法,它采用分治法 (Divide and Conquer) 的思想,将待排序的数组分成两个子数组,然后递归地对子数组进行排序,最后将两个有序的子数组合并成一个有序的数组。

归并排序的时间复杂度为 $O(n \log n)$,而且性能十分稳定,不受输入数据的影响,代价是需要额外的内存空间。

1 算法步骤

归并排序有递归和迭代两种实现方式(需要通过递归实现的算法,都可以转换为迭代法),但核心算法都一样,步骤如下:

  1. 申请空间 temp,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
  2. 设定两个指针 lr,最初位置分别为两个已经排序序列的起始位置;
  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
  4. 重复步骤 3 直到某一指针达到序列尾;
  5. 将另一序列剩下的所有元素直接复制到合并序列尾。

2 代码实现

2.1 递归法实现

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
public class MergeSort {
    public static void mergeSort(int[] arr) {
        if (arr == null || arr.length <= 1) {
            return;
        }
        // 申请容量为 左右子序列长度和 的临时空间
        int[] temp = new int[arr.length];
        mergeSort(arr, 0, arr.length - 1, temp);
    }

    /**
     * @param arr 原始数组
     * @param start 子序列头索引
     * @param end 子序列尾索引
     * @param temp 申请的容量为 左右子序列长度和 的临时空间
     */
    private static void mergeSort(int[] arr, int start, int end, int[] temp) {
        if (start < end) {
            int mid = (start + end) / 2;
            // 左边归并排序,使得左子序列有序
            mergeSort(arr, start, mid, temp);
            // 右边归并排序,使得右子序列有序
            mergeSort(arr, mid + 1, end, temp);
            // 将两个有序子数组合并操作
            merge(arr, start, mid, end, temp);
        }
    }

    /**
     * @param arr 原始数组
     * @param start 待合并的左序列头索引
     * @param mid 待合并的左序列尾索引(也是右序列头索引的前一个索引)
     * @param end 待合并的右序列尾索引
     * @param temp 申请的容量为 左右子序列长度和 的临时空间
     */
    private static void merge(int[] arr, int start, int mid, int end, int[] temp) {
        int l = start; // 左序列指针
        int r = mid + 1; // 右序列指针
        int t = 0; // 临时数组指针
        while (l <= mid && r <= end) {
            if (arr[l] <= arr[r]) {
                temp[t++] = arr[l++];
            } else {
                temp[t++] = arr[r++];
            }
        }

        // 将左序列剩余元素填充进 temp 中
        while (l <= mid) {
            temp[t++] = arr[l++];
        }
        // 将右序列剩余元素填充进 temp 中
        while (r <= end) {
            temp[t++] = arr[r++];
        }
        t = 0;
        // 将 temp 中的元素全部拷贝到原数组中
        while (start <= end) {
            arr[start++] = temp[t++];
        }
    }
}

在递归法实现中,我们首先判断数组是否为空或者长度小于等于 1,如果是,则直接返回。然后创建一个临时数组 temp,并递归调用 mergeSort 方法进行归并排序。

mergeSort 方法中,我们首先找到数组的中间位置 mid,然后递归调用 mergeSort 方法对左右两个子序列进行归并排序,最后调用 merge 方法将两个有序子数组合并成一个有序数组。

merge 方法中,我们使用三个指针 lrt 来遍历左右两个子序列和临时数组,并将较小的元素放入临时数组中。最后,将临时数组中的元素拷贝回原数组中。

2.2 迭代法实现

迭代法中的 Merge 操作与递归法完全一致,只是将上层的递归操作换成了双层循环,源码如下:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
public static void mergeSort(int[] arr) {
    if (arr == null || arr.length <= 1) {
        return;
    }
    int n = arr.length;
    int[] temp = new int[n];
    for (int size = 1; size < n; size *= 2) {
        for (int start = 0; start < n - size; start += 2 * size) {
            int mid = start + size - 1;
            int end = Math.min(start + 2 * size - 1, n - 1);
            merge(arr, start, mid, end, temp);
        }
    }
}

在迭代法实现中,我们首先判断数组是否为空或者长度小于等于 1,如果是,则直接返回。然后创建一个临时数组 temp,并使用两个循环进行迭代。

外层循环的变量 size 表示每次归并的子序列的长度,初始值为 1,每次乘以 2,直到 size 大于等于数组的长度。内层循环的变量 start 表示当前归并的左子序列的起始位置,每次增加 2 倍的 size

在内层循环中,我们根据 startmidend 的值调用 merge 方法进行归并操作。merge 方法实现同递归法完全一样。

3 归并排序递归过程演示

归并排序示意图