希尔排序

希尔排序希尔排序是插入排序的一种又称“缩小增量排序”，是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。是直接插入排序算法的一种改进，减少了其复制的次数，速度要快很多。 原因是，当n值很大时数据的每一趟排序需要移动的个数很少，但数据项的距离很长。当n值减小时每一趟需要移动的数据增多，此时已经接近于它们排序后的最终位置。 正是这两种情况的结合才使希尔排序效率比插入排序高很多。

希尔排序的代码也是相当的简练，下面是Java代码实现

 public static void sort(int a[]){//
        int N = a.length;
        int h = 1;
        while (h<N/3){//1
            h=h*3+1;
        }
        while (h>=1){//2
            for (int i = h; i < N; i++) {//3
                int nowVal = a[i];//4
                int insert = i-h;//5
                while (insert>=0&&a[insert]>nowVal){//6
                    a[insert+h]=a[insert];//7
                    insert-=h;//8
                }
                a[insert+h]=nowVal;//9
            }
            h/=3;//10
        }


    }

下面一步一步解释一下

• 1.需要一个初始的长度来进行小范围的插入排序。这里取h为总长度的三分之一，取值的大小与算法的时间复杂度直接相关。假如大小为N则从最大值开始分组插入排序，可能会适得其反，假如大小从1开始那么就完全是插入排序了。
• 2.h最小值为1
• 3.从h开始到N-1，每一组的距离都为h，这里把所有距离为h的都循环到了
• 4.设置哨兵单位（和插入排序一样）
• 5.设置插入位置（同插入排序）
• 6.插入位置大于等于0，判断insert位置的元素与哨兵元素的大小
• 7.假如6条件满足则将组内后一位设置成当前值（将当前值向后移动一位）
• 8.插入点向左h单位（插入排序向左1单位）
• 9.将判断出的插入点设置为哨兵值。（由于上一个循环最后减去h所以这里要加上h）
• 10.减少h值，这里可以设置成别的减少值。