数据结构与算法——希尔排序

        希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法。希尔排序也是一种插入排序，它是简单插入排序经过改进之后的一个更高效的版本，也称为缩小增量排序。

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

 小结：1.第一次分组，每组相邻两个元素下标相差5

            2.第二次分组，每组相邻两个元素下标相差2

            3.第三次分组，每组相邻两个元素下标相差1

//插入时采用交换法
    public static void shellSort1(int[] arr) {
        int temp = 0;
        //分组次数为1时，完成排序
        for (int g = arr.length / 2; g > 0; g = g / 2) {
            for (int i = g; i < arr.length; i++) {
                for (int j = i - g; j >= 0; j -= g) {
                    if (arr[j] > arr[j + g]) {
                        temp = arr[j];
                        arr[j] = arr[j + g];
                        arr[j + g] = temp;
                    }
                }
            }
        }
    }

测试排序80000条数据时间：9秒

 //插入时采用位移法
    public static void shellSort2(int[] arr) {
        // 增量gap, 并逐步的缩小增量
        for (int gap = arr.length / 2; gap > 0; gap /= 2) {
            // 从第gap个元素，逐个对其所在的组进行直接插入排序
            for (int i = gap; i < arr.length; i++) {
                int j = i;
                int temp = arr[j];
                if (arr[j] < arr[j - gap]) {
                    while (j - gap >= 0 && temp < arr[j - gap]) {
                        //移动
                        arr[j] = arr[j-gap];
                        j -= gap;
                    }
                    //当退出while后，就给temp找到插入的位置
                    arr[j] = temp;
                }
            }
        }
    }

测试排序80000条数据时间：不到1秒