希尔排序（插排的优化）

4.希尔排序（相对较快,不稳定）

思想：

先确定一个间隔，我们从0开始，每经过一个间隔取一个数，把这些数分成一组，把这一组数用插入排序排好。然后将间隔逐渐变小，循环该过程。

为什么比插入排序的效率高？

因为如果1在比较后面的位置，它要排到最前面必须经过很多次交换。如果用希尔排序，因为有间隔，所以只需要很少的次数就能把1排到前面。这就是它能提高效率的地方。希尔排序也叫改进排序。

希尔排序在间隔较大的时候交换的次数比较少，间隔小的时候交换的距离比较近。但希尔排序是跳着排的，所以不稳定。

实现：

//希尔排序(也叫改进排序,是对插入排序的改进;时间复杂度为n**1.3,空间为1,不稳定)
//思想:将插入排序的每次插入后一个改成间隔为n的插入;
//即:逻辑上将间隔为N的数取出来组成一个新的数组,然后进行插入排序
//然后逐渐将间隔减小,最终使用间隔为1的时候即为插入排序
//因为是跳着排的,所以希尔排序不稳定
//改进点:1.间隔大时,每次交换的步数变大了
//      2.间隔小时,交换的次数变少了
//N最大取多少:1.希尔第一次N取数组长度的1/2,每次为N*1/2
//          2.Knuth序列 n=3k+1(<=length) 初始k=1;一般会更快
int k=1;
while(3*k+1<a.length){
    k=3*k+1;
}
while(k>0)
{
    for (int j = k; j < a.length; j++) {
         //一次以k为间隔的插入排序
        for (int i = j; i > k - 1; i-=k) {
            if (a[i] < a[i - k]) swap(a, i, i - k);
        }
    }
    k=(k-1)/3;
}