【数据结构与算法】系列二十五 - 归并排序

发表于 | 分类于
| 字数统计 1.2k 字 | 阅读时长 4 分钟

…

一、归并排序

归并排序（Merge Sort）在1945年由约翰·冯·诺伊曼（John von Neumann）首次提出。

执行流程：

  1. 不断地将当前序列平均分割成2个子序列，直到不能再分割（序列中只剩1个元素）
  2. 不断地将2个子序列合并成一个有序序列，直到最终只剩下1个有序序列。

1.1. 分割（divide）

数据分割比较容易理解，就是一个不断分隔递归的过程。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
  * 对 [begin, end) 范围的数据进行归并排序
  */
private void sort(int begin, int end) {
  // 元素只有0个或1个时，不排序
  if (end - begin < 2) return;
  
  // 取出中间分割点
  int mid = (begin + end) >> 1;
  // 对中间点的左边数据继续分割（递归）
  sort(begin, mid);
  // 对中间点的右边数据继续分割（递归）
  sort(mid, end);
  // 上面分割完成后，开始合并数据
  merge(begin, mid, end);
}

/**
  * 将 [begin, mid) 和 [mid, end) 范围的序列合并成一个有序序列
  */
private void merge(int begin, int mid, int end) {
  // 合并代码（重点）...
}

1.2. 合并（merge）

假设分割成了左右两个序列，左右两边分别用一个指针指向待排序位置，比较两个指针位置的数据，把较小的数据放入到排序好的数组中，然后把对应较小位置的指针往后移动，反复进行比较，最终就会形成一个有序的数据列。

下面以部分数据为例，看一下分割后的数据是如何进行合并的：

但是实际上，归并排序有以下条件限制：

  1. 需要merge的2组序列存在于同一个数组中，并且是挨在一起的（同一块内存）。

  1. 为了更好地完成merge操作，最好将其中1组序列备份出来，比如[begin, mid)（因为排序好的数据最终覆盖的是左边，所以把左边的数据进行备份，备份数据和右边数据进行合并操作）

1
2
3
4
5
// 简写：li(left-index)、le(left-end)、ri(right-index)、re(right-end)
li == 0
le == mid – begin
ri == mid
re == end

没有必要每次都创建一块内存来备份左边的数据，只需要创建一个原数组长度一半的数组即可（长数组可以容纳短数组的数据）。

在合并时，还需要有一个排序数组指针ai(array-index)，指向下一次要插入的位置。

合并时考虑左边先遍历结束和右边先遍历结束的场景。

左边先结束：
如果左边先结束，右边数组元素不需要动。

右边先结束：

如果右边先结束，左边的元素依次放入右边数组中。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
private void merge(int begin, int mid, int end) {
  int li = 0, le = mid - begin;
  int ri = mid, re = end;
  int ai = begin;
  
  // 备份左边数组
  for (int i = li; i < le; i++) {
    // 是begin + i，而不是 i，因为是递归调用，begin是从0开始的但不一定是0
    leftArray[i] = array[begin + i];
  }
  
  // 如果左边还没有结束
  while (li < le) { 
    // ri < re 表示操作右边的数据
    if (ri < re && array[ri] < leftArray[li]) {
      array[ai++] = array[ri++];
    } else { // 右边先结束
      array[ai++] = leftArray[li++];
    }
  }
}

注意：array[ri] <= leftArray[li]就会失去稳定性。

1.3. 复杂度分析

由于涉及到递归调用，计算复杂度会比较复杂。

归并排序时，用到两次递归，每次递归消耗时间都是n/2，合并操作是O(n)，我们只需要计算出递归消耗的时间。

递归时间复杂度计算步骤：

  1. 假设递归消耗的时间用T(n)表示，则一次归并排序所花费的时间是：

    1
    T(n) = 2 * T(n/2) + O(n)

  2. 如果n == 1：

    1
    T(1) = O(1)

  3. 等式两边同时除以n：

    1
    T(n)/n = T(n/2)/(n/2) + O(1)

  4. 令S(n) = T(n)/n：

    1
    2
    3
    4
    5
    6
    7
    8
    S(1) = O(1)
    S(n) = S(n/2) + O(1)
         = S(n/4) + O(2)
         = S(n/8) + O(3)
         = ...
         = S(n/(2^k)) + O(k) 
         = S(1) + O(logn)
         = O(logn)

  5. 综上可以得出：

    1
    T(n) = n * S(n) = O(nlogn)

由于归并排序总是平均分割子序列，所以最好、最坏、平均时间复杂度都是O(nlogn) ，属于稳定排序。

从代码中不难看出：归并排序的空间复杂度是O(n/2+logn) = O(n)，n/2用于临时存放左侧数组，logn是因为递归调用。

常见的递推式与复杂度：

二、LeetCode