基础算法-希尔排序

今天学习相对于选择和插入排序性能更加稳定的排序算法：希尔排序。
PS：如果你看到的内容不全，原谅我为了日更做“预”更新，我一定会在第二天早上8点前补充完成，过了这周就好了。

题目介绍

题目沿用选择和插入的内容吧：给定一个数组，将数组按从小到大顺序排序。题目理解起来也是很容易的，就不再画图介绍了。

希尔排序

希尔排序的思想是使数组任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。换句话说，一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组。

实现代码

因在之前文章实现过排序抽象类，因此希尔排序类只要继承抽象类即可。

public class Shell extends AbstractSort {

    @Override
    public void sort(Comparable[] a) {
        int N = a.length;
        int h = 1;
        while (h < N / 3) h = 3 * h + 1; // 1,4,13,40,121,364,1093,...
        while (h >= 1) { //将数组变为h有序
            for (int i = h; i < N; i++) {
                //将a[i]插入到a[i-h],a[i-2*h],a[i-3*h]...之中
                for (int j = i; j >= h && less(a[j], a[j - 1]); j -= h) {
                    exch(a, j, j - h);
                }
            }
            h = h / 3;
        }
    }
}

算法相关实现源码地址：https://github.com/xiekq/rubs-algorithms