二分查找的递归解法：
public class BinarySearch {
public static void main(String[] args) {
// TODO Auto-generated method stub
}
/**
* 选择其中之一个子问题求解
*/
private static int binarySearch(int []arr,int low,int high,int key){
if (low>high) {
return -1;
}
int mid = low + ((high-low)>>1); // (high-low)>>1 向右移一位，相当于除2 防止溢出，移位也更高效。
int midVal = arr[mid];
if (midVal<key) {
return binarySearch(arr, mid+1, high, key);
}else if (midVal>key) {
return binarySearch(arr, low, high-1, key);
}else {
return mid; // key found
}
}
}
希尔排序：
import java.util.Arrays;
public class ShellSort {
public static void main(String[] args) {
int [] arr = {9,8,7,6,5,4,3,2,1};
shellSort(arr);
System.out.println(Arrays.toString(arr));
}
/**
* 希尔排序是插入排序的一种
* 也称缩小增量排序，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法
* 思路： 如序列 9 8 7 6 5 4 3 2 1
* 确定一个增量序列，如 4（length/2） 2 1 ，从大到小使用增量
* 使用第一个增量，将序列划分为若干个子序列，下标组合为0-4-8，1-5，2-6，3-7
* 依次对子序列使用直接插入排序法
* 使用第二个增量，将序列划分为若干个子序列0-2-4-6-8，1-3-5-7
* 依次对子序列使用直接插入排序法
* 使用第三个增量1，这时子序列就是源序列0-1-2-3-4-5-6-7-8，使用直接插入法
* 完成排序
* 时间复杂度： 不太确定 在O(nlogn) ~ O(n的平方)之间
* 空间复杂度：O(1)
* 原址排序
* 稳定性：由于相同的元素可能会被划分至不同子序列单独排序，因此稳定性是无法保证的------不稳定
*
*/
static void shellSort(int[]arr){
// 不断地缩小增量
for (int interval = arr.length/2; interval > 0; interval = interval/2) {
// 增量为interval的插入排序
for (int i = interval; i < arr.length; i++) {
int target = arr[i];
int j = i - interval;
while(j>-1&&target<arr[j]){
arr[j+interval] = arr[j];
j -= interval;
}
arr[j+interval] = target;
}
}
}
}