希尔排序

1.希尔排序

希尔排序法又称缩小增量法，它的基本思想：

1. 先选定一个整数 gap，把待排序文件中所有记录分成 gap 个组，所有距离为 gap 的记录分在同一组内，并对每一组内的元素进行排序。
2. 然后将 gap 逐渐减小重复上述分组和排序的工作。
3. 当到达 gap=1 时，所有元素在同一组内排好序。

2. 算法原理

1.将数的个数设为 n，取奇数 k=n/2，将下标差值为 k 的数分为一组，构成有序序列； 2.再取 k=k/2 ，将下标差值为 k 的数分为一组，构成有序序列； 3.重复第二步，直到 k=1 执行简单插入排序；

3. 代码

/**
 * 排序器接口(策略模式: 将算法封装到具有共同接口的独立的类中使得它们可以相互替换)
 */
public interface Sorter<T extends Comparable<T>> {

    /**
     * 排序
     *
     * @param array 待排序的数组
     */
    default void sort(T[] array) {
    }
}

public class ShellSorter<T extends Comparable<T>> implements Sorter<T> {
    public void sort(T[] array) {
        int length = array.length;

        //分组数
        int gap = length / 2;
        while (gap > 0) {
            //把距离为gap的元素编为一个组，扫描所有组
            for (int i = gap; i < length; ++i) {
                int j = i - gap;

                //对距离为gap的元素组进行排序
                while (j >= 0 && array[j + gap].compareTo(array[j]) < 0) {
                    T temp = array[j];
                    array[j] = array[j + gap];
                    array[j + gap] = temp;

                    j -= gap;
                }
            }
            gap /= 2;
        }
    }
}

4. 总结

希尔排序的特性总结：

1. 希尔排序是对直接插入排序的优化，它是不稳定的。
2. 当 gap > 1 时都是预排序，目的是让数组更接近于有序。当 gap == 1 时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
3. 空间复杂度 O(1)。
4. 时间复杂度取决于 gap 序列的选取，最好情况为 O(nlogn)，最坏情况为 O(n^2)，平均约为 O(nlogn)。
5. 希尔排序没有大量的移位操作，因此即使数组很大，其性能也不差。