希尔排序

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

算法实现：希尔排序需要定义一个增量，一般会选择增量为gap=length/2，缩小增量以gap=gap/2的方式，这个增量可以用一个序列来表示，{n/2,(n/2)/2…1}，称为增量序列，这个增量是比较常用的，也是希尔建议的增量，称为希尔增量。

（1）对于一个大小为10的无序数组[81，92，11，72，22，31，52，4，61，0]来说，我们初始增量为gap=length/2=5，所以这个数组要被分为5组，分别是[81，31]，[92，52]，[11，4]，[72，61]，[22，0]，对这5组分别进行，则小的元素就被调换到了前面，然后再缩小增量gap=gap/2=2。

代码实现:

public class ShellSort {

    public static void main(String[] args) {

        //定义一个大点的数组，测试希尔排序需要多长时间
        // 给8w个随机数排序
        int arr[] = new int[80000];
        //随机生成数
        for (int i = 0; i < arr.length; i++) {
            //生成0~100w之间的随机数
            arr[i] = (int) (Math.random() * 1000000);
        }

        /*System.out.println("排序前");
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("%d%c", arr[i], (i + 1) % 10 == 0 ? 
 : 32);
        }*/

        long startTime = Long.valueOf(String.valueOf(System.currentTimeMillis()));
        fastShellSort(arr);
        long endTime = Long.valueOf(String.valueOf(System.currentTimeMillis()));

        /*System.out.println("
排序后");
        for (int i = 0; i < arr.length; i++) {
            System.out.printf("%d%c", arr[i], (i + 1) % 10 == 0 ? 
 : 32);
        }*/

        System.out.println("
优化后的希尔排序(移位法)给" + arr.length + "个数据排序的时间(ms)为:" + (endTime - startTime)); 
    }

 
    /**
     * 实现优化后的希尔排序(移位法)，从小到大排序
     *
     * @param arr
     */
    private static void fastShellSort(int[] arr) {
        // 定义一个增量
        int len = arr.length / 2;
        while (len > 0) {
            for (int i = len; i < arr.length; i++) {
                int insertIndex = i - len;
                int insertVal = arr[i];
                // if (insertVal < arr[insertIndex]) {
                while (insertIndex >= 0 && insertVal < arr[insertIndex]) {
                    arr[insertIndex + len] = arr[insertIndex];
                    insertIndex -= len;
                }
                arr[insertIndex + len] = insertVal;
                //  }
            }
            len = len / 2;
        }
    }
}

可以从结果看出希尔排序比直接插入排序算法的速度快了很多倍。