码上游记

hongjian.xia的个人博客

0%

归并排序（Merge Sort）

发表于 更新于 分类于
本文字数： 2.2k 阅读时长 ≈ 2 分钟

概述

归并排序是一种时间复杂度为$ O (N\log N) $的排序算法，使用的是 分治 的策略。
算法的基本操作是合并两个已经排序的序列，因为两个序列是已经排序了的，所以将它们按顺序复制到第三个序列中，可以通过一次遍历完成。
所以将原序列使用递归不断的分成两个子序列，直至序列中是元素个数为1，此时序列为已经排序完成的，将两个子序列合并，得到一个排序完成的序列，再继续合并，直至整个序列都是已排序的。

算法实现

算法实现主要包含两个过程：将序列从指定的开始到结束位置的子序列排序，合并两个有序的序列
算法是用递归实现的，递归的边界为：指定的结束位置和和结束位置相同，此时子序列只有一个元素，显然子序列为已排序的。
完整实现代码参见：MergeSort

子序列排序

1
2
3
4
5
6
7
8
9
10
11
private static <T extends Comparable<? super T>> void mergeSort(T[] eles, T[] temp, int begin, int end) {
    if (begin == end) { // 开始位置与结束位置相同时，序列则已经排序完成
        return;
    }
    int middle = (begin + end) / 2;
    // 将序列分为两个子序列，分别排序后再合并
    mergeSort(eles, temp, begin, middle);
    mergeSort(eles, temp, middle + 1, end);
    // 合并两个排序完成的子序列
    merge(eles, temp, begin, middle + 1, end);
}

合并子序列

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
private static <T extends Comparable<? super T>> void merge(T[] eles, T[] temp, int leftPos, int rightPos, int rightEnd) {
    int tempIndex = leftPos;
    int leftEnd = rightPos - 1;
    int lIndex = leftPos;
    int rIndex = rightPos;
    
    while (lIndex <= leftEnd && rIndex <= rightEnd) {
        if (eles[lIndex].compareTo(eles[rIndex]) <= 0) {
            temp[tempIndex++] = eles[lIndex++];
        } else {
            temp[tempIndex++] = eles[rIndex++];
        }
    }
    // 处理left剩余的元素
    while (lIndex <= leftEnd) {
        temp[tempIndex++] = eles[lIndex++];
    }
    
    // 处理right剩余的元素
    while (rIndex <= rightEnd) {
        temp[tempIndex++] = eles[rIndex++];
    }
    // 将排序后的结果复制会原数组
    for (int i = leftPos; i <= rightEnd; i++) {
        eles[i] = temp[i];
    }
}

算法入口

1
2
3
public static <T extends Comparable<? super T>> void sort(T[] eles) {
    mergeSort(eles, (T[])new Comparable[eles.length], 0, eles.length - 1);
}

算法分析

假设为题规模$N$为2的幂，这样我们可以将它分为连个相等的部分。对于$N = 1$，归并排序所用的时间为常数，我们将它记为1（这个常数是多少并不会影响到最终得到的时间复杂度，这里使用1方便于计算）。
对于N归并排序的时间等于完成两个大小为 $N/2$ 的归并排序所用的时间加上合并的时间，合并所用的时间为线性的。所以有下列等式：

由于$N$为2的幂，所以将等式1中的$N$用$N/2$替换，并将等式两侧同时乘以2，则可以得到

从而得到

再将$N/4$带入等式1，同样能得到

所以我们有

以此类推，我们将能得到

其中 $k = \log N$, 所以

因此归并排序的时间复杂度为 $O(N\log N)$。

此证明中令$N$为2的幂，可以简化计算，当$N$不为2的幂时计算略有不同，但得到的时间复杂度仍未$O(N\log N)$。

思考

  1. 归并排序的非递归实现
  2. 如何不使用额外的内存空间完成排序

参考

MarkAllenWeiss. 数据结构与算法分析:Java语言描述-第3版[M]. 机械工业出版社, 2016, 193-198