什么是分治算法？( 二 ) _分治算法

代码实现：
public class Test { public static void main(String[] args) { int[] arr = { 1, 2, 3, 4 }; fullSort(arr, 0, arr.length - 1); } public static void fullSort(int[] arr, int start, int end) { // 递归终止条件 if (start == end) { for (int i : arr) { System.out.print(i); } System.out.println(); return; } for (int i = start; i <= end; i++) { swap(arr, i, start); fullSort(arr, start + 1, end); swap(arr, i, start); } } private static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }}6.3 归并排序
归并排序：归并（Merge）排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。即先划分为两个部分，最后进行合并。

文章插图

归并排序
伪代码：
算法 MergeSort(A, p, r)输入：数组A[p...r]输出：有序数组Aif(p < r) then q <- (p+r)/2//折半划分 MergeSort(A, p ,q)//子问题1 MergeSort(A, p ,q)//子问题2 Merge(A, p ,q, r)//合并求解代码实现：
public class MergeSort { //两路归并算法，两个排好序的子序列合并为一个子序列 public void merge(int []a,int left,int mid,int right){ int []tmp=new int[a.length];//辅助数组 int p1=left,p2=mid+1,k=left;//p1、p2是检测指针，k是存放指针 while(p1<=mid && p2<=right){ if(a[p1]<=a[p2]) tmp[k++]=a[p1++]; else tmp[k++]=a[p2++]; } while(p1<=mid) tmp[k++]=a[p1++];//如果第一个序列未检测完，直接将后面所有元素加到合并的序列中 while(p2<=right) tmp[k++]=a[p2++];//同上 //复制回原素组 for (int i = left; i <=right; i++)a[i]=tmp[i]; } public void mergeSort(int [] a,int start,int end){ if(start<end){//当子序列中只有一个元素时结束递归 int mid=(start+end)/2;//划分子序列 mergeSort(a, start, mid);//对左侧子序列进行递归排序 mergeSort(a, mid+1, end);//对右侧子序列进行递归排序 merge(a, start, mid, end);//合并 } }}6.4 快速排序
快速排序的基本思想：当前待排序的无序区为 A[low..high]，利用分治法可将快速排序的基本思想描述为：
（1）分解：
在A[low..high]中任选一个记录作为基准(pivot)，以此基准将当前无序区划分为左、右两个较小的子区间R[low..pivotpos-1) 和 R[pivotpos+1..high]，并使左边子区间中所有记录的关键字均小于等于基准记录(不妨记为pivot)的关键字 pivot.key，右边的子区间中所有记录的关键字均大于等于pivot.key，而基准记录pivot则位于正确的位置( pivotpos )上，它无须参加后续的排序。
（2）求解：
通过递归调用快速排序对左、右子区间R[low..pivotpos-1]和R[pivotpos+1..high]快速排序。
（3）合并：
因为当"求解"步骤中的两个递归调用结束时，其左、右两个子区间已有序。对快速排序而言，"组合"步骤无须做什么，可看作是空操作。

文章插图

快速排序
代码实现：
#include <IOStream>using namespace std;void QuickSort(int arr[], int low, int high){ if (high <= low) return; int i = low; int j = high + 1; int key = arr[low]; while (true) { /*从左向右找比key大的值*/ while (arr[++i] < key) { if (i == high){ break; } } /*从右向左找比key小的值*/ while (arr[--j] > key) { if (j == low){ break; } } if (i >= j) break; /*交换i,j对应的值*/ int temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; } /*中枢值与j对应值交换*/ int temp = arr[low]; arr[low] = arr[j]; arr[j] = temp; QuickSort(arr, low, j - 1); QuickSort(arr, j + 1, high);}6.5 汉诺塔
汉诺塔（Hanoi Tower）问题也是一个经典的递归问题，该问题描述如下：