分治算法搞起。。。
分治算法
简介
分治算法是一种很重要的算法,字面上的解释是“分而治之”,就是把一个复杂的问题分解成两个或更多的相同或相似的子问题 … 直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并,这个技巧就是很多高效算法的基础,如排序算法(快速排序,归并排序),傅里叶变换(快速傅里叶变换)…
分治算法的三个步骤
1. 分解:将原问题分解为若干个规模较小的问题,相互独立,与原问题形式相同的子问题
2. 解决:若子问题规模较小则直接解决,否则递归地解各个子问题
3. 合并:将各个子问题的解合并为原问题的解
代码实现(快速排序)
public static int[] quickSort(int[] arr) {sort(arr, 0, arr.length - 1);
return arr;
}
public static void sort(int[] arr, int left, int right) {
// 首先判断是否应该退出递归
if (left > right) {return;}
// 找到基准数
int base = arr[left];
int i = left;
int j = right;
// 循环操作
while (i != j) {
// 从右向左查找,找到比 base 大的数
while (arr[j] >= base && i < j) {j--;}
// 从左向右查找,找到比 base 小的数
while (arr[i] <= base && i < j) {i++;}
// 上面循环结束了,说明已经找到了 i 和 j 的值,这里需要进行判断是否符合要求,然后进行替换
if (i < j) {int num = arr[i];
arr[i] = arr[j];
arr[j] = num;
}
// 这时候需要将基准数放到中间位置
arr[left] = arr[i];
arr[i] = base;
// 进行递归操作
sort(arr, left, j - 1);
sort(arr, i + 1, right);
}
}
public static void main(String[] args) {System.out.println(Arrays.toString(quickSort(new int[]{4, 3, 2, 7, 5, 88, 33})));
}
说实话,我这个还是有点不太明白,这里我先消化一下,然后回过来写一下。
个人网站链接
http://www.zhouzhaodong.xyz