算法学习之路（4）——插入排序与希尔排序

1、插入排序

　　插入排序非常类似于整扑克牌。在开始摸牌时，左手是空的，牌面朝下放在桌上。接着，一次从桌上摸起一张牌，并将它插入到左手一把牌中的正确位置上。为了找到这张牌的正确位置，要将它与手中已有的牌从右到左地进行比较。无论什么时候，左手中的牌都是排好序的。

示例代码：

private static boolean less(Comparable v,Comparable w){
    return v.compareTo(w)<0;
}
    
private static void exchange(Comparable[] a,int i,int j){
    Comparable t = a[i];
    a[i] = a[j];
    a[j] = t;
}

/**
 * 插入排序
 * @param array
 */
public static void insertSort(Comparable[] array){
    int len = array.length;
    for(int i = 1;i<len;i++){
        for(int j = i;j>0 && less(array[j], array[j - 1]);j--){
            exchange(array,j,j-1);
        }
    }
}

　　对于大规模乱序数组，插入排序的速度很慢，因为它只会交换相邻的元素，因此元素只能一点一点地从数组的一端移动到另一端。例如，如果主键最小的元素正好在数组的尽头，要将它挪到正确的位置就需要N-1次移动。

2、希尔排序

　　希尔排序是简单改进了的插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。希尔排序的思想是使数组中任意间隔为h的元素都是有序的。排序示例：

                                         

实现希尔排序的方法是对于每个h，用插入排序将h个子数组独立地排序。因此，只需要在插入排序的代码中将移动元素的距离由1改为h即可。

代码示例：

/**
 * 希尔排序
 * @param array
 */
public static void shellSort(Comparable[] array){
    int len = array.length;
    int h = 1;
    while(h < len/3) h = 3*h + 1;
    while(h >= 1){
        for(int i = h;i<len;i++){
            for(int j = i;j>=h && less(array[j],array[j-h]);j-=h){
                exchange(array,j,j-h);
            }
        }
                h = h/3;
    }
}

注： 

while(h < len/3) h = 3*h + 1;

为选择初始的步长，读者也可以自定义步长。