复习一下直接插入排序，具体思想就不多说了，大家懂的。
在这算法都是用java写，感觉不是很专业，应该用C写，算了，无所谓啦！
代码存在弊端，不够猛或者不够劲，哪里的判断多余，赋值多余，循环多余，欢迎指出，不怜赐教。
import java.util.Arrays;public class InsertSort {public static void main(String[] args) {int[] arr = {1, 33, 55, 77, 60, 42, 83, 83, 73, 48, 85} ;insertSort(arr) ;System.out.println(Arrays.toString(arr)) ;int[] arr1 = {1, 33, 55, 77, 60, 42, 83, 83, 73, 48, 85} ;binarySort(arr1) ;System.out.println(Arrays.toString(arr1)) ;}/*** 直接插入排序* @param s*/public static void insertSort(int[] s) {// 从数组下标1的位置循环到结尾int x ;for (int i = 1; i < s.length; i++) {// 保存当前i下标的值x = s[i] ;// 循环查找小于i下标的值for (int j = 0; j < i; j++) {// 情况1：数组长度为2时执行if(i-1 == 0 && x < s[j]) {s[i] = s[j] ;s[j] = x ;// 情况2：数组长度>2时执行}else {// 当前数比x大，那么x前面到j下标的数往后移，再将j下标的数替换为x，// 这里记住要breakif(s[j] >= x) {for (int j2 = i; j2 > j; j2--) {s[j2] = s[j2-1] ;}s[j] = x ;break ;}}} // System.out.println(Arrays.toString(s)) ; }}/*** 折半插入排序依赖的是已知有顺序的数列，* 在这里风格有点不同，但思想还是一样的。* @param s*/private static void binarySort(int[] s) {int x ;if(s.length == 2) {if(s[0] > s[1]) {x = s[0] ;s[0] = s[1] ;s[1] = x ;}}else if(s.length > 2) {for (int i = 2; i < s.length; i++) {binarySort(s, s[i], 0, i-1) ;}}}/*** * @param s 当前要排序的数组* @param x 要插入数组的值* @param l 已排序好的数组的左下标* @param r 已排序好的数组的右下标*/private static void binarySort(int[] s, int x, int l, int r) {/*** 这种情况是x比已排序的数列第一个数小，那么直接将x插入到数列首位*/if(x < s[l]) {for (int i = r+1; i > l; i--) {s[i] = s[i-1] ;}s[l] = x ;/*** 这种情况是x比最后一个数大，那么直接将x插入到数列最末尾*/}else if(x > s[r]) {s[r+1] = x ;/*** 这里就是经典的二分插入了*/}else {int rTemp = r ;int m ;while(l < r) {m = (l + r) / 2 ;if(x < s[m]) {r = m - 1 ;}else {l = m + 1 ;}}if(x > s[l]) {l++ ;} // System.out.println("l" + l + ",,," + "r" + r) ;for (int i = rTemp+1; i > l; i--) { // System.out.println("s[i]" + s[i] + ",,," + "s[i-1]" + s[i-1]) ;s[i] = s[i-1] ; // System.out.println(Arrays.toString(s)) ; } // System.out.println(l) ;s[l] = x ;}} }
思想详见：http://baike.baidu.com/view/396887.htm
参考博客：http://www.cnblogs.com/GavinDai/archive/2011/12/02/2271998.html