1.分治算法介绍
1）分治法是一种很重要的算法。
字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题…….直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法（快速排序，归并排序），傅立叶变换（快速傅立叶变换）。
2）分治算法可以求解的一些经典问题
- 二分搜索
- 大整数乘法
- 棋盘覆盖·
- 合并排序·
- 快速排序
- 线性时间选择
- 最接近点对问题
- 循环赛日程表
- 汉诺塔
3)分治算法的基本步骤
分治法在每一层递归上都有三个步骤：
- 分解：将原问题分解为若干个规模较小，相互独立，与原问题形式相同的子问题
- 解决：若子问题规模较小而容易被解决则直接解，否则递归地解各个子问题
- 合并：将各个子问题的解合并为原问题的解。
4)分治算法应用
1.汉诺塔
思路分析:1）如果是有一个盘,n=1的情况，A->C
如果我们有n>=2情况，我们总是可以看做是两个盘1.最下边的盘2.上面的盘
1）先把最上面的盘A->B
2）把最下边的盘A>C
3）把B塔的所有盘从B->C
public class Hanoitower {
static int count=0;
public static void main(String[] args) {
hanoitower(100,'A','B','C');
System.out.println("一共需要："+count+"步");
}
/**
* 汉诺塔的递归方法求解
* @param num 表示盘的个数
* @param a 表示从该塔开始
* @param b 用于辅助的塔
* @param c 目标是移动到该塔
*/
public static void hanoitower(int num,char a,char b,char c) {
//如果是有一个盘,n=1的情况，A->C
if(num==1) {
System.out.println("第"+num+"盘从 "+a+"->"+c);
}else {
//1）先把最上面的盘A->B,其中c塔作为辅助
hanoitower(num-1,a,c,b);
//2）把最下边的盘A>C
System.out.println("第"+num+"盘从 "+a+"->"+c);
//3）把B塔的所有盘从B->C 其中a塔作为辅助
hanoitower(num-1,b,a,c);
}
count++;
}
}
2.快速排序
快速排序法介绍：
快速排序（Quicksort）是对冒泡排序的一种改进。基本思想是：通过一趟排序将要排序的数据分割成独立的两部分，其中一部分的所有数据都比外一部分的所有数据都要小，然后再按此方法对这两部分数据分别进行快速排序，整个排序过程可以递归进行，以此达到整个数据变成有序序列。
public class QuickSort {
public static void main(String[] args) {
int[] arr= {7,8,-9,5,8,6,1,44,8,8};
quickSort(arr,0,arr.length-1);
System.out.println(Arrays.toString(arr));
}
public static void quickSort(int[] arr,int leftIndex,int rightIndex) {
if(leftIndex>=rightIndex) {
return;
}
//选取第一个数做为基准
int key=arr[leftIndex];
int left=leftIndex;//左下标
int right=rightIndex;//y右下表
while(left<right) {
while(arr[right]>=key&&right>left) {
//从右往左扫描，找到第一个数比基准小的元素
right--;
}
while(arr[left]<=key&&left<right) {
//从左往右扫描，找到第一个比基准值大的元素
left++;
}
//当left<right时进行交换
if(left<right) {
int temp=arr[left];
arr[left]=arr[right];
arr[right]=temp;
}
}
//将基准数归位，即放在left的位置上，左边的数比基准数小，右边的数比基准数大
arr[leftIndex]=arr[left];
arr[left]=key;
//对基准值的左边的元素进行递归
quickSort(arr,leftIndex,left-1);
//对基准值右边的元素进行递归排序
quickSort(arr,left+1,rightIndex);
}
}
3.合并排序
归并排序是一种稳定的排序算法，归并排序的主要问题在于它需要一个与待排序数组一样大的辅助数组空间。由于归并排序每次划分时两个子序列的长度基本一样，所以归并排序最好、最差和平均时间复杂度都是nlog2n。
//递归分开与合并
public static void mergSort(int arr[],int start,int end) {
if(start>=end) {
return ;
}
int mid=(start+end)/2;
mergSort(arr,start,mid);//
mergSort(arr,mid+1,end);
merg(arr,start,mid,end);//排序和合并
}
/**排序并且合并
* @param arr 要排序的数组
* @param start 头检查指针
* @param mid 中间检查指针
* @param end 尾指针
*/
public static void merg(int[] arr,int start,int mid,int end) {
int[] temp=new int[arr.length];//辅助指针
int p1=start;//检测指针
int p2=mid+1;//检测指针
int index=start;//用于记录temp的索引
while(p1<=mid&&p2<=end) {
//比较两个数
if(arr[p1]<=arr[p2]) {
//存储在temp数组中
temp[index++]=arr[p1++];
}else {
temp[index++]=arr[p2++];
}
}
//将数组剩下的数放到临时数组中
while(p1<=mid) {
temp[index++]=arr[p1++];
}
while(p2<=end) {
temp[index++]=arr[p2++];
}
//将temp数组复制到arr数组中
for(int i=start;i<=end;i++) {
arr[i]=temp[i];
}
}
参考:尚硅谷Java数据结构和java算法，韩顺平数据结构和算法
https://blog.csdn.net/qq_36186690/article/details/82470451
https://blog.csdn.net/qq_36442947/article/details/81612870
网友评论