前言

点击查看算法介绍

五大算法

• 分治算法
• 动态规划
• 贪心算法
• 回溯算法
• 分支限界算法

WX搜素”Java长征记”对这些算法也有详细介绍。

分治算法

一、算法概述

    简单来说，分治算法就是“分而治之”，即就是讲一个规模很大很复杂的问题分 成若干份相同或相似的更小的子问题，直到最后可以简单的直接求解，将所有子问题 的解合并即得到原问题的解。 

二、分治策略的基本思想

• 将原始问题划分或者归结为规模较小的子问题
• 递归或迭代求解每个子问题 将子问题的解综合得到原问题的解

注意：

• 子问题与原问题的性质必须一致
• 子问题必须可以独立求解
• 递归停止时，子问题必须能直接求解

三、时间复杂性分析

在分治算法中，假设原问题总规模为n，我们假设分解和合并所用时间为C(n)和D(n),假设W(x)为处理一个规模为x的问题所用的时间。每一个子问题是原问题规模的1/a。

如果原问题规模<=最小子问题的规模，既可以直接求解，那么其时间复杂度是一个常数。否则，W(n)=aW(n/a)+C(n)+D(n);

四、分治思维

简单来说就是由小到大，先理清最小子问题如何去解决，然后逐渐增加问题规模，找到递归或者迭代方法，编写程序。

五、经典例子

• 二分归并排序
• 汉诺(Hanoi)塔
• 快速排序
• 二分检索
• 查找第k大元素

如果想获得以下这些景点例子的文本形式的代码，WX搜索”Java长征记“，回复”算法代码“即可。

●二分归并排序

设计思想：

1、将规模为n的原问题划分为规模为n/2的子问题；
2、继续划分，划分至规模为n/4的，继续一直到规模为1，可以直接求解，这块分治就结束了；
3、从规模1到n/2依次陆续归并排好序的子数组，直到原始数组。

伪码：

算法 Merge Sort (A, p, r)
输入：数组 A[ p … r]
输出：元素按从小到大排序的数组 A

1. if p < r
2. then q <-( p + r)/2 对半划分子问题
3. Merge Sort (A, p, q) 子问题1
4. Merge Sort (A, q+1, r) 子问题2
5. Merge (A, p, q, r) 综合解

程序：

//归并排序 public static void mergeSort(int[] nums,int begin,int end){ /* int length=nums.length;         if(length<=1){             return;         }         if(end<=begin){             return;          }*/ int length=end-begin+1; if(length<=1){ return; } /*分*/ int mid=(begin+end)/2; mergeSort(nums, begin, mid); mergeSort(nums, mid+1, end); /*治*/ merge(nums, begin,mid, end); } public static void merge(int[] nums,int begin,int mid,int end){ if(mid>=end){ return; } int length=end-begin+1; int[] temp=new int[length]; int k=0; int i=begin; int j=mid+1; while(i<=mid&&j<=end){ if(nums[i]<nums[j]){                 temp[k]=nums[i];                 i++; } else{                 temp[k]=nums[j];                 j++; }             k++; } /*传进来前半部分已经排完*/ if(i>mid){ while(j<=end){                 temp[k]=nums[j];                 j++;                 k++; } } /*后半部分已排完*/ if(j>end){ while(i<=mid){                 temp[k]=nums[i];                 i++;                 k++; } } /*重新存进原数组*/ for(int m=0;m<length;m++){             nums[begin+m]=temp[m]; } } 

图解:

合并排序部分细节图解

时间复杂度分析:

假设原问题规模为n，二分归并排序最坏情况： W(n)=2W(n/2)+n-1 其中子问题最小规模为1，W(1)=1;

W(n)=nlogn – n + 1
时间复杂度为O(nlogn)

●汉诺(Hanoi)塔

游戏介绍

在汉诺塔游戏中，有三个塔座：A、B、C。几个大小各不相同，从小到大一次编号的圆盘，每个原盘中间有一个小孔。最初，所有的圆盘都在A塔座上，其中最大的圆盘在最下面，然后是第二大，以此类推.

该游戏的目的是将所有的圆盘从A塔移到B塔;C塔用来放置临时圆盘,游戏的规则如下:

• 一次只能移动一个圆盘
• 任何时候都不能将一个较大的圆盘压在较小的圆盘上面.
• 除了第二条限制,任何塔座的最上面的圆盘都可以移动到其他塔座上.

设计思想

游戏分析：

假设共有n个盘子 当n=1，盘子记为1，直接将1从A移到C塔即可；

当n=2，盘子从小到大记为1，2，先将1从A移到B，再将2移到C，最后将1移到C塔即可；

当n=3，盘子从小到大记为1，2，3，此刻只需将1,2看为一个盘子即可，记为1+2，先将1+2移至B塔，2在下1在上，然后将3移到C塔，最后将1+2盘移到C塔；

当1+2盘移到C塔时，由于每次只能动一个盘子，所以可以看做一个新的只有两个盘的Hanoi游戏。 …

当n=n，盘子从小到大依次记为1,2,3…n-1,n,此刻将1到n-1看为一个盘，移到到C塔，再将n移到C，最后将1到n-1看为一个新的Hanoi游戏移到C塔，依次类推到只有1个盘子（盘子1）。

设计思想：

• 将原问题归结为规模为 n-1 的2个子问题.
• 继续归约，将原问题归结为规模为n-2 的 4 个子问题. 继续…，当子问题规模为1时，归约过程截止
• 从规模 1到 n-1，陆续组合两个子问题的解. 直到规模为n.

伪码：

算法 Hanoi (A, C, n) // n个盘子A到C

1. if n=1 then move (A, C) //1个盘子A到C
2. else Hanoi (A, B, n-1)
3. move (A, C)
4. Hanoi (B, C, n-1) 设 n个盘子的移动次数为 T(n)
   T(n) = 2 T(n-1) + 1，
   T(1) = 1， T
   (n)=2n-1

程序：

//hanoi塔 public static void solve(int n) { hanoi(n, "A", "B", "C"); // 已知条件n个圆盘和A、B、C三个塔 } /**       * 若要让第n个圆盘成功从A塔移动到C塔，需要让前n-1个圆盘先从A塔移动到B塔，然后让第n个圆盘从A塔移动到C塔，       * 最后让第n-1个圆盘从B塔移动到C塔，至于如何将前n-1个圆盘从A塔移动到B塔或者从A塔移动到C塔，仅仅是和父问题相同的子问题       * 采用父问题的解决方案即可。       */ private static void hanoi(int n, String a, String b, String c) { if (n == 1) { // 只有一个圆盘时直接从A塔移到C塔 move(n, a, c); } else { hanoi(n - 1, a, c, b);// 将前n-1个圆盘从A塔移到B塔        move(n, a, c); // 将第n个圆盘从A塔移到C塔             hanoi(n - 1, b, a, c);//看为一个新的hanoi塔游戏， 将前n-1个圆盘从B塔移到C塔，A塔为中间塔 } } private static void move(int n, String i, String j) {          System.out.println("第" + n + "个圆盘，" + "从" + i + "塔移动到" + j+"塔"); } 

时间复杂度分析

hanoi塔游戏的递推公式为T（n）=2T（n-1)+1，时间复杂度为O(2^n)

●快速排序

设计思想

找一个基准数，将比其小的放置左边大的放置右边，然后再将基准数前后部分按照此方法继续分开，直至只有1个数时停止分裂，将所有的子序列合起来即排序完成

伪码：

算法：quicksort(Arr,p,r) 输入：数组Arr[p…r] 输出：元素按从小到大排序的数组 Arr
1.if p < r then q<- partition(Arr,p,r)
quicksort(Arr,p,q-1)
quicksort(Arr,p+1,r) }
2.else return 其中partition（Arr,p,r）就是分治部分。

部分图解

例，快速排序的一次递归运行

程序：

//快速排序 public static void quickSort(int[] num, int begin, int end){ if(begin<end) { int reference = num[begin];//将区间的收元素作为基准数 int index=begin;//记录初始参考数下标 int i=begin;//从左开始寻找比基准数小的元素 int j=end;//从右开始寻找比基准数大的元素 while(i<j) { while(i<j && num[j]>=reference)               j--; while(i<j && num[i]<=reference)               i++; swap(num,i,j);//交换i,j } swap(num,i,index);//将参考数放置中间(分界线处左小右大) quickSort(num,begin,i-1); quickSort(num,i+1,end); } else return ; } public static void swap(int num[],int i,int j) { int temp;      temp=num[i];      num[i]=num[j];      num[j]=temp; } 

时间复杂度分析

快速排序的时间复杂度为O(n2)

●二分检索

设计思想

• 通过 x 与中位数的比较，将原问题归结为规模减半的子问题，如果 x 小于中位数，则子问题由小于 x 的数构成，否则子问题由大于 x的数构成.
• 对子问题进行二分检索
• 当子问题规模为 1 时，直接比较 x与 T[m]，若相等则返回 m，否则返回 -1.

伪码：

算法 Binary Search (T, l, r, x) 输入：数组 T，下标从 l 到 r，查找数 x 输出：j // 若x在T 中,
j 为下标; 否则为 -1

1. l<-1; r<-n
2. while l<=r do
3. m<-(l +r)/2 // m为中间位置
4. if T[m]=x then return m // x是中位数
5. else if T[m]>x then r<-m-1
6. else l<-m+1
7. return -1

程序：

//二分检索 public static int BinarySearch(int num[],int begin,int end,int x) { if(x>num[end]||x<num[begin]||begin>end||num==null) return -1; int mid=(begin+end)/2; if(num[mid]==x) return mid; else if(num[mid]>x) return BinarySearch(num,begin,mid-1,x); else if(num[mid]<x) return BinarySearch(num,mid+1,end,x); else return -1; } 

【针对于有序序列，所以在二分检索前要对数组中元素进行排序，可直接调用Arrays.sorrt(a);进行排序】

时间复杂度分析：

W(n) = W ( n/2 ) +1，W(1) = 1
解出W(n)= log n + 1，算法时间复杂度为O(log n)。

●查找第k大元素

设计思想

随机确定一个数组下标，将对应的元素作为参考数，然后将比该数大的元素放在其左边并且记录其左区间元素数量（count从1开始计数），小于等于的置于其右，若k小于参考数前面的元素数量，则第k大的数在左区间，否则在右区间（在右区间寻找第k-count大的数），然后再继续归约，直到k==count

伪码：

find(A,left,right,k)

输入：数组 A，下标从 left 到 right，第几大k

输出：数组A中对应的第k大的数
1.partition（A，left，right）
2.if k<count
then find(A,left,middle-1,k)
3.else if k>count
then find(A,middle+1,end,k-count)
4.else return A[midlle] partition为分区，计数部分。

程序：

//找第k大的数 public static int find(int a[],int left,int right,int k) { int temp; int index = (int)Math.random()*a.length; //随机选取一个下标的元素作为定值来进行比较 //swap(a[left],a[index]);         temp=a[left];         a[left]=a[index];         a[index]=temp; int middle = left; int count = 1; //记录比选定元素大的元素的个数 int i; for(i = left+1;i<=right;i++) //计算所选定的元素左边的元素的个数 { if(a[i]>a[left]) //将大的元素排在所选定点得左边 { //swap(a[middle],a[i]);                 temp=a[middle];                 a[middle]=a[i];                 a[i]=temp;                 count++;                 middle++; } } /*分治*/ if(k<count){ //如果需要找的第k个大的元素小于左边的元素数量，那么第k个大的元素在左边这个区间，再递归调用去找 return find(a,left,middle-1,k); } else if(k>count){ //如果大于左边元素数量，则在右边区间找 return find(a,middle+1,right,k-count); } else return a[middle]; //如果k==count说明要找的元素刚好是middle } 

时间复杂度分析

时间复杂度为O(n);

干货

想了解更多的算法、数据结构以及关于Java基础知识的，WX搜索”Java长征记“