希尔排序

希尔排序一种基于插人排序的快速的排序算法，对于大规模乱序数组插入排序很慢，因为它只会交换相邻的元素，因此元素只能一点点地从数组的一端移动到另一端。 例如，如果主键最小的元素正好在数组的尽头，要将它挪到正确的位置就需要N-1次移动。希尔排序为了加快速度简单地改进了插入排序，交换不相邻的元素以对数组的局部进行排序，并最终用插入排序将局部有序的数组排序。

希尔排序的思想是使数组中任意间隔为h的元素都是有序的。这样的数组被称为h有序数组。或者说一个h有序数组就是h个互相独立的有序数组编织在一起组成的一个数组。在进行排序时，如果h很大，我们就能将元素移动到很远的地方，为实现更小的h有序创造方便。用这种方式，对于任意以1结尾的h序列，我们都能够将数组排序。这就是希尔排序。

public class Shell
{
    public static void sort(Comparable[] a)
    {
        int N = a.length;
        int h = 1;
        while (h < N/3) h = 3*h + 1;
        while (h >= 1)
        {   
            for(int i = h; i < N; i++)
            {
                for(int j = i; j >= h && less(a[j],a[j-h]); j -= h)
                exch(a, j, j-h);
            }
            h = h/3;
        }
    }
}

在上面这个算法中我们使用了序列1/2( -1)。从N/3开始递减至1.我们把这个序列称之为递增序列
实现希尔排序的一种方法是对于每一个h，用插入序列将h个子数组独立地排序。但因为子数组是相互独立的，一个更加简单的方法是在h子数组中将每个元素交换到比它大的元素之前去（将比它大的元素向右移动一格）。只需要在插入排序的代码中将移动元素的距离由1改为h就可以了。这样子就可以将希尔排序的实现转换为一个类似插入排序的算法，只不过使用的增量不同。
那么如何选择递增序列？算法的性能不仅却决于h，还取决于h之间的数学性质，比如它们的公因子等等。有很多论文研究了各种不同的递增序列，但是都无法证明某个序列是“最好的”。在我们上面这个算法中递增序列的计算和使用都很简单，和复杂递增序列的性能接近。