分治算法（归并排序、一维点对、HDU-1007）

分治算法的基本思想是将一个规模为N的问题分解为K个规模较小的子问题，这些子问题相互独立且与原问题性质相同。求出子问题的解，就可得到原问题的解。

分治法解题的一般步骤：

分解，将要解决的问题划分成若干规模较小的同类问题；求解，当子问题划分得足够小时，用较简单的方法解决；合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。

在认识分治之前很有必要先了解一下递归，当然，递归也是最基本的编程问题，一般接触过编程的人都会对递归有一些认识.为什么要先了解递归呢？你看，根据上面所说的，我们就要将一个问题分成若干个小问题，然后一一求解并且最后合并，这就是一个递归的问题，递归的去分解自身，递归的去解决每一个小问题，然后合并…

关于递归，这里举一个最简单的例子，求N！，代码如下：

public int getFactorial(int n) { if (n == 1) { return n; } else { return n * getFactorial(n-1); } }

有了递归的铺垫，我们开始看看分治算法相关的一些常见问题：

1、归并排序

归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。

首先要把需要排序的数组分解成若干个小数组，直到不可再分为止，之后再将这些小数组通过简单的比较排序之后进行合并，下面先看看合并数组的示例：

package sort; public class SortTest { public static void main(String[] args) { int[] num1 = {1, 3, 4, 7, 9}; int[] num2 = {2, 5, 7, 10}; int[] numMeger = new int[num1.length + num2.length]; MegerArray(num1, num2, num1.length, num2.length, numMeger); for (int i = 0; i < numMeger.length; i++) { System.out.print(numMeger[i] + " "); } } public static void MegerArray(int[] num1, int[] num2, int n1, int n2, int[] numMeger) { int i = 0; int j = 0; int k = 0; while (i < n1 && j < n2) { if (num1[i] < num2[j]) { numMeger[k++] = num1[i++]; } else { numMeger[k++] = num2[j++]; } } while (i < n1) { numMeger[k++] = num1[i++]; } while (j < n2) { numMeger[k++] = num2[j++]; } } }

有了之前递归和合并的前提之后就可以进行归并排序了，基本思路就是将数组分成二组A，B，如果这二组组内的数据都是有序的，那么就可以很方便的将这二组数据进行排序。如何让这二组组内数据有序了？

可以将A，B组各自再分成二组。依次类推，当分出来的小组只有一个数据时，可以认为这个小组组内已经达到了有序，然后再合并相邻的二个小组就可以了。这样通过先递归的分解数列，再合并数列就完成了归并排序。 示例如下：

package sort; public class SortTest { public static void main(String[] args) { int[] num = {2, 8, 4, 7, 10, 9, 14}; int[] numSort = new int[num.length]; mergeSort(num, 0, num.length-1, numSort); for (int i = 0; i < num.length; i++) { System.out.print(num[i] + " "); } System.out.println(); for (int i = 0; i < numSort.length; i++) { System.out.print(numSort[i] + " "); } } public static void mergeSort(int[] num, int first, int last, int[] temp) { if (first < last) { int mid = (first + last) / 2; mergeSort(num, first, mid, temp); mergeSort(num, mid+1, last, temp); MegerArray(num, first, mid, last, temp); } } public static void MegerArray(int[] num, int first, int mid, int last, int[] temp) { int i = first; int j = mid+1; int m = 0; while (i <= mid && j <= last) { if (num[i] < num[j]) { temp[m++] = num[i++]; } else { temp[m++] = num[j++]; } } while (i <= mid) { temp[m++] = num[i++]; } while (j <= last) { temp[m++] = num[j++]; } for (int n = 0; n < m; n++) { num[first + n] = temp[n]; } } }