C/C++描述 - 分治法及归并排序

  将两个有序的子数组合并为一个整体有序的数组跟幼稚园里小朋友排队的道理差不多。假设小一班和小二班的小朋友已经按照身高由低到高排好队了，你是幼儿园老师，需要将小一班和小二班的队列合并为按身高由低到高的单一队列，那么，你很容易得到下述算法：比较排头位的两位小朋友的身高，将其中较矮的小朋友“拉”到新的队列中去；重复上述过程直至两个队列的小朋友都被拉完为止。如果其中一个队列的小朋友提前被拉完，那么另一个队列的剩余小朋友依次拉入新队列即可。

版权声明

本文可以在互联网上自由转载，但必须：注明出处(作者：海洋饼干叔叔)并包含指向本页面的链接。

本文不可以以纸质出版为目的进行改编、摘抄。

  通常而论，问题的求解难度和计算量通常随问题规模的增加而增大，随问题规模的减小而减小，且当问题的规模充分小时，问题易于求解。比如，10个数的排序问题比5个数的排序问题要复杂，而1个数的排序问题则易于求解，因为只包含1个元素的数组天然有序。这给我们提供了一种称之为分治法（device and conquer）的算法设计思路。

  分治法的解题思路可以简单概括如下：

• 当问题的规模较大，难以直接求解时，将问题拆分成2个或者多个规模较小的相同性质的子问题。

• 分别对子问题进行递归求解，如果子问题的规模仍然较大，继续拆分成规模较小的子子问题。

• 将子问题的解合并为原问题的解。

  将分治法应用于排序问题，即为归并排序算法。归并排序（merge sort）的计算复杂性较冒泡排序要低一个数量级，其解题思路可概要如下：

• 当待排序数组的元素个数大于1时，认为该问题过于复杂，难以求解，将数组拆分成两个差不多大的子数组。

• 分别对拆分出来的子数组进行排序，得到有序的两个子数组。对子数组的排序过程是递归的，当子数组的元素个数大于1时，会进一步拆分成更小的子子数组。

• 将两个有序的子数组合并为整体有序的“原”数组。

  图7-4展示了数组[8,4,2,9,5,3,1,7]的归并排序过程。首先是“分”，由于数组含有8个元素难以直接排序，将其分成两个子数组，分别是[8,4,2,9]和[5,3,1,7]。这些这些子数组仍然过大，递归拆分成8个仅包含1个元素的子数组，分别是[8]、[4]、[2]、[9]、[5]、[3]、[1]、[7]。由于1个元素的数组天然有序，这8个子数组都可视为有序数组。

  接下来是“治”，将有序的子数组两两合并，[8]、[4]合并为[4,8]，[2]、[9]合并为[2,9]，[4,8]和[2,9]又合并为[2,4,8,9]，… [2,4,8,9]和[1,3,5,7]最终合并为原问题的解[1,2,3,4,5,7,8,9]。容易看出，在归并排序里，真正的排序工作是在子数组合并的过程中完成的。

  归并排序的实现请见下述程序。

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

//Project - MergeSort
#include <cstdio>
#include <cstdlib>

void merge(int a[],int low, int mid, int high) {
    int* t = (int*)malloc((high-low+1)*sizeof(int));
    int i = low, j = mid+1, k = 0;
    while (i<=mid && j<=high){
        if (a[i]<=a[j])
            t[k++] = a[i++];
        else
            t[k++] = a[j++];
    }
    while (i<=mid)
        t[k++] = a[i++];
    while (j<=high)
        t[k++] = a[j++];
    for (i=low,k=0;i<=high;i++,k++)
        a[i] = t[k];
    free(t);
}

void mergeSort(int a[], int low, int high) {
    if (low<high){
        int mid = (low+high)/2;
        mergeSort(a,low,mid);
        mergeSort(a,mid+1,high);
        merge(a,low,mid,high);
    }
}

int main() {
    int v[8] = {8,4,2,9,5,3,1,7};
    mergeSort(v,0,7);
    printf("Sorted: ");
    for (int i=0;i<8;i++)
        printf("%d ",v[i]);
    return 0;
}

上述程序的执行结果为：

1

Sorted: 1 2 3 4 5 7 8 9

  对上述程序的正确理解需要从相关函数的接口说起。

🚩第34行：对数组v[0,7]进行归并排序，即对数组v中下标0至下标7的部分进行归并排序。

🚩第24行：如果下标low小于high，说明当前子问题至少有两个以上的元素，过于复杂，应进行分治。否则，当前子问题仅包含1个元素，天然有序，什么都不用做。

🚩第25 ~ 27行：将子问题分解成规模差不多大的两个子问题a[low,mid]和a[mid+1,high]，然后分别递归调用mergeSort()函数进行求解。在第26行、第27行的mergeSort()函数执行后，a[low,mid]和a[mid+1,high]分别递增有序，对应着两个子问题的解。再次说明，在C++中，整数除以整数的商为整数，小数部分会被舍弃。

🚩第28行：执行merge()函数将两个有序子数组a[low,mid]和a[mid+1,high]合并至a[low,high]。

  接下来讨论merge()函数的工作原理。将两个有序的子数组合并为一个整体有序的数组跟幼稚园里小朋友排队的道理差不多。假设小一班和小二班的小朋友已经按照身高由低到高排好队了，你是幼儿园老师，需要将小一班和小二班的队列合并为按身高由低到高的单一队列，那么，你很容易得到下述算法：比较排头位的两位小朋友的身高，将其中较矮的小朋友“拉”到新的队列中去；重复上述过程直至两个队列的小朋友都被拉完为止。如果其中一个队列的小朋友提前被拉完，那么另一个队列的剩余小朋友依次拉入新队列即可。

🚩第6行：动态分配一个临时的数组空间t，用于暂存有序的结果数组。从下标low至下标high,共有high–low+1个元素。

🚩第20行：释放临时数组t。

🚩第7行：整数i赋值为左子数组的首元素下标，整数j赋值为右子数组的首元素下标，整数k则为临时结果数组t的当前操作下标。

  图7-5表示子数组a[0,3]和a[4,7]合并过程中的一个中间状态。下标i指向4，说明左子数组中的2已经“拉”到了临时结果数组t；下标j指向5，说明右子数组中的1和3已经“拉”到了临时结果数组t；下标k值为3，说明t[0,2]中已包含了三个有序元素，接下来，程序将比较i所指向的4和j所指向的5，其中的较小者将被复制到t[k]。如果左子数组的元素4被复制，那么i加1，如果右子数组的元素5被复制，则j加1，每复制一个元素，k加1。

🚩第8 ~ 13行：循环比较下标i和下标j所指向的两个子数组的当前待处理元素，将其中较小值复制到t[k]。该循环一直持续到其中一个子数组“耗尽”为止。当i>mid时，说明左子数组耗尽，当j>high时，说明右子数组耗尽。

🚩第14 ~ 17行：前述循环结束后，左子数组或者右子数组可能还有剩余元素，依次复制到t。

🚩第18 ~ 19行：将临时结果数组t的内容复制到a[low,high]。读者需要注意，该for循环的初始化语句被一个逗号操作符分开，i的初始值为low，k的初始值为0；同样地，更新表达式也被逗号操作符分开，更新时，i和k都递增1。在整个循环过程中，i的取值范围为[low,high]，k的取值范围为[0,high-low+1)，其中，high-low+1是结果数组所包含的元素个数。读者如果对该for循环的初始化语句以及测试、更新表达式的含义感到困惑，建议回顾本书4.3节。

  上述工作完成后，a[low,high]即为合并后的有序数组。

总结🍵

  冒泡排序的计算复杂性为θ(n²) ，归并排序的计算复杂性则为θ(nlogn)。显然，后者的阶比前者低一个数量级，归并排序解决排序问题的效率远优于冒泡排序。

  归并排序的计算复杂性分析稍显复杂，本书不作解释，读者可以在《算法分析》课程里学习到相关内容。