1，分治法
- 定义：把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
-
合并排序
image.png
public class MergeSort {
public static void main(String[] args) {
int[] arr = {85,3,52,9,7,1,5,4, 2};
merge(arr);
}
/**
*
* @param arr
*/
static void merge(int[] arr) {
int length = arr.length;
int mid = length / 2;
if (mid == 0) {
return;
}
int[] leftArr= Arrays.copyOfRange(arr,0,mid);//拷贝数组array的左半部分
int[] rightArr=Arrays.copyOfRange(arr,mid,length);//拷贝数组array的右半部分
System.out.println("-----------------------");
System.out.println(JSON.toJSONString(leftArr));
System.out.println(JSON.toJSONString(rightArr));
// 递归至最小单位
merge(leftArr); // 这里把arr变掉了！！找了半天
merge(rightArr);
sort(arr, leftArr, rightArr); // 这里的arr就是每个left,right,,,不要晕
System.out.println("++++++++++++++++++++++");
System.out.println(JSON.toJSONString(arr));
}
/**
* 排序
* @param result
* @param left
* @param right
*/
static void sort(int[] result, int[] left, int[] right) {
int i=0,l=0,r=0;
while(l<left.length&&r<right.length){
if(left[l]<right[r]){
result[i]=left[l];
i++;
l++;
}else{
result[i]=right[r];
i++;
r++;
}
}
while(r<right.length){//如果右边剩下合并右边的
result[i]=right[r];
r++;
i++;
}
while(l<left.length){
result[i]=left[l];
l++;
i++;
}
}
}
打印结果
-----------------------
[85,3,52,9]
[7,1,5,4,2]
-----------------------
[85,3]
[52,9]
-----------------------
[85]
[3]
++++++++++++++++++++++
[3,85]
-----------------------
[52]
[9]
++++++++++++++++++++++
[9,52]
++++++++++++++++++++++
[3,9,52,85]
-----------------------
[7,1]
[5,4,2]
-----------------------
[7]
[1]
++++++++++++++++++++++
[1,7]
-----------------------
[5]
[4,2]
-----------------------
[4]
[2]
++++++++++++++++++++++
[2,4]
++++++++++++++++++++++
[2,4,5]
++++++++++++++++++++++
[1,2,4,5,7]
++++++++++++++++++++++
[1,2,3,4,5,7,9,52,85]
- 快速排序
image.png
public class FastSort {
public static int[] qsort(int arr[],int start,int end) {
if (start > end) {
return arr;
}
int i = start;
int j = end;
int temp = arr[start];
while (i != j) {
while (j > i && arr[j] >= temp) {
j--; // 循环右边直到找到比temp小的值
}
while (j > i && arr[i] <= temp) {
i++; // 循环左边直到找到比temp大的值
}
if (j > i) {
int tem = arr[i]; // 将大值放右边，小值放左边
arr[i] = arr[j];
arr[j] = tem;
}
}
// 这个时候i等于j，互换中间那个数字和temp的位置，因为中间那个值肯定是小于temp的，所以放左边
arr[start] = arr[i];
arr[i] = temp;
qsort(arr, start, i - 1); // 递归处理左边的
qsort(arr, i + 1, end); // 递归处理右边的
return (arr);
}
public static void main(String[] args) {
int arr[] = new int[]{5,3,2,9,8,10,7,6,1,4};
int len = arr.length-1;
arr=qsort(arr,0,len);
for (int i:arr) {
System.out.print(i+"\t");
}
}
}
2，贪心法
- 定义：所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。
- 适用：局部最优策略能导致产生全局最优解。
3，动态规划算法
- 定义：动态规划(dynamic programming)是运筹学的一个分支，是求解决策过程(decision process)最优化的数学方法。20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优化原理(principle of optimality)，把多阶段过程转化为一系列单阶段问题，利用各阶段之间的关系，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。1957年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。
4，回溯法
-定义：回溯法（探索与回溯法）是一种选优搜索法，又称为试探法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。
5，分支限界法
-定义：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。
-对比：分支限界法与回溯法的不同
（1）求解目标：回溯法的求解目标是找出解空间树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。
（2）搜索方式的不同：回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。
