希尔排序

希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序，同时该算法是冲破O(n^2）的第一批算法之一。

基本思想

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。

图1 希尔排序

第一轮排序：设置step步长为4，根据步长将数组分为四组，{1,3}， {4,2}，{6,5}，{0,9} 进行两两比较。
将i=step，开始往后遍历。如果a[i]>a[i-step]交换数据。得到第一轮排序结果：1 2 5 0 3 4 6 9
第二轮排序：设置step步长为2，根据步长继续两两分组，比较数据大小。得到第二轮排序结果：1 0 3 2 5 4 6 9
第三轮排序：设置step步长为1，根据步长继续两两分组，比较数据大小。得到第三轮排序结果：0 1 2 3 4 5 6 9

代码实现

//希尔排序
public static int[] shellSort(int[] a) {
    //设置初始步长
    int step = a.length/2;
    int i, j;
    //while循环将step折半查找，直到step<1跳出循环
    while (step >= 1) {
        //i从step开始遍历
        for (i=step; i<a.length; i++) {
            //保存临时变量
            int temp = a[i];
            //j从i-step开始遍历
            for(j=i-step; j>=0 && temp<a[j]; j=j-step) {  //第三个参数，j-step始终负，跳出循环
                //j+step实际就是i的位置，即i-step+step
                a[j+step] = a[j];
            }
            //这里的j+step 实际是j的位置，即j-step+step
            a[j+step] = temp;
        }
        step = step/2;
    }
    return a;
}

public static void main(String[] args) {
    int[] a = {1, 4 , 6, 0, 3, 2, 5, 9};
    int[] b = shellSort(a);
    System.out.print("Shell sort:\n");
    for(int i=0; i<a.length; i++) {
        System.out.print(b[i] + ", ");
    }
}

输出结果：
Shell sort:
0, 1, 2, 3, 4, 5, 6, 9,

希尔排序的关键并不是随便分组后各自排序，而是将相隔某个step 的记录组成一个子序列， 实现跳跃式的移动，使得排序的效率提高。
希尔排序的时间复杂度是O（nlogn），效率上比冒泡排序，直接插入排序，简单选择排序的O（n^2）要高。