分治法

使用分治法解决问题的基本步骤是:


归并排序

归并排序的核心是:将两个连续的、各自有序的子序列合并成一个有序的子序列。

归并(array, start, mid, end) {
  // array[start...mid] 有序
  // array[mid+1...end] 有序
  // 最终使 array[start...end] 有序
  i = start;
  j = mid + 1;
  cursor = 0;
  temp_array = 长度是两个子序列长度之和的辅助数组;

  while (i <= mid && j <= end) {
    if array[i] <= array[j]
      temp_array[cursor++] = array[i++];
    else
      temp_array[cursor++] = array[j++];
  }

  如果第一个子序列没处理到头,则将第一个子序列中剩余的元素复制到 temp_array 的尾部;
  如果第二个子序列没处理到头,则将第二个子序列中剩余的元素复制到 temp_array 的尾部;

  将 temp_array 复制到 array[start...end];
}

上面的算法是将子问题的解合并成原问题的解的方式,下面是一个分解-归并的整体过程的示例:

归并排序

下面的伪代码是归并排序的递归实现:

归并排序(array, start, end) {
  if (end <= start)
    长度为 1 的子序列直接有序,直接返回;

  // 将子序列一分为 2,然后分别使用归并排序进行排序
  mid = (start + end) / 2;
  归并排序(array, start, mid);
  归并排序(array, mid+1, end);

  // 然后归并两个有序序列
  归并(start, mid, end);
}

时间复杂度

归并过程的时间复杂度是:n。

根据递归程序的时间复杂度计算公式,可得:

T(n) = 2 * T(n/2) + n ===>
T(n) = 2 * (2 * T(n/4) + n/2) + n ===>
T(n) = 4 * T(n/4) + 2 * n ===>
T(n) = 4 * (2 * T(n/8) + n/4) + 2 * n ===>
T(n) = 8 * T(n/8) + 3 * n ===>
...
T(n) = (2^m) * T(n/(2^m)) + m * n

且T(1) = 1

也就是当 n / (2^m) -> 1,即 m -> log2n 时,
T(n) = n + n * log2n
所以归并排序的时间复杂度是 O(nlogn)

空间复杂度

在归并时,用到了辅助数组,所以归并排序不是原地排序,其空间复杂度是 O(n)


Python 实现

tim-chow的 Gitub