递归-之二分查找与选择排序算法
中提到Spring aop的拦截器调用链采用递归的方式实现；
之所以本篇单独将递归单独提出来讨论，是觉得递归是一种重要的编程思想；不只是设计原则或者设计模式那种方法论，递归是一种解决问题的思想，其核心是拆解分而治之，将一个大而复杂的问题分解多个小问题，如果分解出来的某些小问题还是无所适从，那么继续分解，直到分解到可以实现为止；
不断分解的过程就是递归思想；递归的思想就是细化问题，直到复杂的问题分解多个简单的小问题；
递归的外观：自己调用自己直到达到某个条件为止，然后依次退出每个方法。
看起来像方法栈的调用，每调用一个方法即压入一个栈帧，直到最后某个方法完成，然后就弹出返回到上一个栈帧，直到全部弹出。
Spring aop的拦截器调用链执行时就具有递归外观；不断调用invocation.proceed();直到拦截器处理完找到最终的invocation执行后依次返回退出；
快速排序；
如何使用递归思想对数组排序呢？
for (int i = 0; i < arr1.length; i++) {
for (int j = i; j < arr1.length; j++) {
if (arr1[i] > arr1[j]){
int temp = arr1[i];
arr1[i] = arr1[j];
arr1[j] = temp;
}
}
}
在没有递归思想时，大家都习惯于使用更直观的方式来处理排序问题；例如使用上面这个冒泡排序；
冒泡排序非常直观：循环数组，将当前值与后面的值逐个比较，每当后面的值比当前值小时，那么“冒泡”；没经过一轮循环当前被循环的值一定后续值中最小的；当全部循环完成，那么就完成了整个数组的排序；
怎么使用递归思想呢？
两个问题：要分解什么？分解到什么程度为止？
要分解什么？即问题对象是什么？数组排序？数组？排序？
问题的对象是数组，对数组排序；
数组分解到什么程度为止？在数组长度大于一个时，才存在排序一说；如果数组中只有一个数，或者数组本来就是空的那就不用排序了，也可以说这种情况的数组是已经排序好的！
所以对于一个长数组，如果使用递归，不断将其切短，直到每个数组只有一个或者一个都没有时，那么整个数组不就自动排好了吗。
private static void quick_sort(int s[], int l, int r)
{
if (l < r)
{
int i = l, j = r,x = s[l];
while (i < j)
{
while(i < j && s[j] >= x) {
// 从右向左找第一个小于x的数
j--;
}
s[i] = s[j];
while(i < j && s[i] < x) {
// 从左向右找第一个大于等于x的数
i++;
}
s[j] = s[i];
}
// x 作为比较基准，将其取出缓存之后，相当于给数据交换数据挪出了空位；
// 之后每一次交换，都使得主动交换发起者位置的数据沦为过时数据，依旧作为下一次的交换空位；
// 流程：留出空位，从右向左找第一个小于x的数，与空位交换，使得当前位置空位，正好可以开始从左向右找第一个大于等于x的数交给这个空位；然后循环此过程；
s[i] = x;
// 递归调用
quick_sort(s, l, i - 1);
quick_sort(s, i + 1, r);
}
}
在快速排序的时候，每一次都只是将数组分解为三个数组而已，这三个数组是相对有序的，但是每个小数组是不是有序的不知道；
三个数组分别为(s, l, i - 1)，(s, i, i)，(s, i + 1, r)；
只要每次拆解出来的三个数组是相对有序，那么如果继续拆解每个小的数组直到无法拆解为止（长度小于2），那么整个数组就是有序的了！
二分查找：
二分查找的前提是数组有序。
普通的查找方法是循环遍历(时间复杂度为o(n))：
private static int get(int[] arr1, int t) {
for (int i = 0; i < arr1.length; i++) {
if (t == arr1[i]){
return i;
}
}
return -1;
}
既然是排序好的数据，采用递归思想；
依旧可以像快速排序一样将数据一分为三：(s, l, i - 1)，(s, i, i)，(s, i + 1, r)；
每次都和s(i)比较，如果不是那么只需要从其他两个数组中的一个里面查找即可了，找到这个数组又一分为三循环上述过程，直到数组无法拆分为止；每一次查找都少了一半要标记计算的数据，时间复杂度o(nlogn)
// Like public version, but without range checks.
private static int binarySearch0(int[] a, int fromIndex, int toIndex,
int key) {
int low = fromIndex;
int high = toIndex - 1;
while (low <= high) {
int mid = (low + high) >>> 1;
int midVal = a[mid];// 中间值
if (midVal < key)
low = mid + 1;// 在右边继续寻找 如果使用递归调用：binarySearch0(a, mid+1, a.length, key);
else if (midVal > key)
high = mid - 1;// 在右边继续寻找
else
return mid; // key found 找到
}
return -(low + 1); // key not found. 找不到
}
jdk中的二分查找使用的是递归思想，并没有递归调用；这样效率更高一点，少了多层递归调用进栈出栈的过程；