排序：插入排序，折半插入排序，希尔排序

复习一下直接插入排序，具体思想就不多说了，大家懂的。

在这算法都是用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，
                     // 这里记住要break
                     if(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