Java七大排序详解-希尔排序

希尔排序

希尔排序又称为缩小增量法。希尔排序法的基本思想是：先给定一个整数gap，把待排序文件中所有的记录分为多个组，所有距离为gap的记录分为一组，并对每一组的记录进行排序 然后重复上诉操作直到gap= 1时 所有记录都排好序了
动图表示如下：

代码如下：

//希尔排序
    public static void shellSort(int[] array) {
        int gap = array.length;
        while (gap > 1) {
            gap = gap / 2; //或者可以写成 gap = gap / 3 + 1
            shell(array, gap);
        }
    }

    private static void shell(int[] array, int gap) {
        //每组的数据都在变化
        for (int i = gap; i < array.length; i++) {
            int tmp = array[i];
            int j = i - gap;
            for (; j >= 0; j -= gap) {
                if (array[j] > tmp) {
                    array[j + gap] = array[j];

                } else {
                    break;
                }
                array[j + gap] = tmp;
            }
        }
    }

时间复杂度：希尔排序的时间复杂度 是不好计算的 他会根据gap的取值的不同而不同。通过大量的实验，现在时间复杂度只能在O(n^1.25) ~O(1.6*n^1.25)来计算。
空间复杂度：O(1);
希尔排序是快速排序的优化 ，希尔排序是不稳定的。