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);//拷貝數(shù)組array的左半部分
int[] rightArr=Arrays.copyOfRange(arr,mid,length);//拷貝數(shù)組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--; // 循環(huán)右邊直到找到比temp小的值
}
while (j > i && arr[i] <= temp) {
i++; // 循環(huán)左邊直到找到比temp大的值
}
if (j > i) {
int tem = arr[i]; // 將大值放右邊，小值放左邊
arr[i] = arr[j];
arr[j] = tem;
}
}
// 這個時候i等于j，互換中間那個數(shù)字和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，貪心法
- 定義：所謂貪心算法是指，在對問題求解時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是在某種意義上的局部最優(yōu)解。
- 適用：局部最優(yōu)策略能導致產生全局最優(yōu)解。
3，動態(tài)規(guī)劃算法
- 定義：動態(tài)規(guī)劃(dynamic programming)是運籌學的一個分支，是求解決策過程(decision process)最優(yōu)化的數(shù)學方法。20世紀50年代初美國數(shù)學家R.E.Bellman等人在研究多階段決策過程(multistep decision process)的優(yōu)化問題時，提出了著名的最優(yōu)化原理(principle of optimality)，把多階段過程轉化為一系列單階段問題，利用各階段之間的關系，逐個求解，創(chuàng)立了解決這類過程優(yōu)化問題的新方法——動態(tài)規(guī)劃。1957年出版了他的名著《Dynamic Programming》，這是該領域的第一本著作。
4，回溯法
-定義：回溯法（探索與回溯法）是一種選優(yōu)搜索法，又稱為試探法，按選優(yōu)條件向前搜索，以達到目標。但當探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標，就退回一步重新選擇，這種走不通就退回再走的技術為回溯法，而滿足回溯條件的某個狀態(tài)的點稱為“回溯點”。
5，分支限界法
-定義：分支限界法常以廣度優(yōu)先或以最小耗費（最大效益）優(yōu)先的方式搜索問題的解空間樹。
-對比：分支限界法與回溯法的不同
（1）求解目標：回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優(yōu)解。
（2）搜索方式的不同：回溯法以深度優(yōu)先的方式搜索解空間樹，而分支限界法則以廣度優(yōu)先或以最小耗費優(yōu)先的方式搜索解空間樹。
