目录
分治法
算法思想
时间效率分析
合并排序
正文
分治法
算法思想
分治法可能是最著名的通用算法设计技术了。虽然它的名气可能和它那好记的名字有关，但它的确是当之无愧的:很多非常有效的算法实际上就是这个通用算法的特殊实现。其实，分治法是按照以下方案工作的。
(1)将一个问题划分为同一类型的若干子问题，子问题最好规模相同。
(2)对这些子问题求解(一般使用递归方法，但在问题规模足够小时，有时也会利用另一个算法)。
(3)有必要的话，合并这些子问题的解，以得到原始问题的答案。
分治法的流程可以参见下图，该图描述的是将一个问题划分为两个较小子问题的例子，也是最常见的情况(至少那些设计运行在单CPU机器上的分治算法是这样的)。
时间效率分析
在分治法最典型的运用中，问题规模为n的实例被划分为两个规模为n/2的实例。更一般的情况下，一个规模为n的实例可以划分为b个规模为n/b的实例，其中α个实例需要求解(这里，a和b是常量，a≥1，b>1)。为了简化分析，我们假设n是b的幂，对于算法的运行时间T(n)，我们有下列递推式:
T(n) =aT(n / b)+ f(n)
其中，f(n)是一个函数，表示将问题分解为小问题和将结果合并起来所消耗的时间(对于求和的例子来说，a = b = 2，f(n)= 1)。上述递推式被称为通用分治递推式(generaldivide-and-conquer recurrence)。显然，T(n)的增长次数取决于常量a和b的值以及函数f(n)的增长次数。在分析许多分治算法的效率时，可以应用下列定理来大大简化我们的工作。
主定理 如果在递推式(5.1)中 f(n)e e(n*)，其中d≥0，那么
合并排序
合并排序是成功应用分治技术的一个完美例子。对于一个需要排序的数组A[0..n -1],合并排序把它一分为二：A[0..[n / 2| - 1]和A[ [n / 2 ]..n-1]，并对每个子数组递归排序，然后把这两个排好序的子数组合并为一个有序数组。
下图演示的是用合并排序算法对数列8,3,2,9,7,1,5,4进行排序的操作过程。
代码实现：
#include <stdio.h> void merge(int arr[], int l, int m, int r) { int i, j, k; int n1 = m - l + 1; int n2 = r - m; /* 创建临时数组 */ int L[n1], R[n2]; /* 复制数据到临时数组 arrays L[] 和 R[] */ for (i = 0; i < n1; i++) L[i] = arr[l + i]; for (j = 0; j < n2; j++) R[j] = arr[m + 1+ j]; /* 归并临时数组到 arr[l..r]*/ i = 0; // 初始化第一个子数组的索引 j = 0; // 初始化第二个子数组的索引 k = l; // 初始归并子数组的索引 while (i < n1 && j < n2) { if (L[i] <= R[j]) { arr[k] = L[i]; i++; } else { arr[k] = R[j]; j++; } k++; } /* 复制 L[] 的保留元素 */ while (i < n1) { arr[k] = L[i]; i++; k++; } /* 复制 R[] 的保留元素 */ while (j < n2) { arr[k] = R[j]; j++; k++; } } /* l 为左侧索引，r 为右侧索引 */ void mergeSort(int arr[], int l, int r) { if (l < r) { // 求中间位置，防止 (l+r) 的和超过 int 类型最大值 int m = l+(r-l)/2; // 递归排序左半部分 mergeSort(arr, l, m); // 递归排序右半部分 mergeSort(arr, m+1, r); // 合并 merge(arr, l, m, r); } }
