希尔排序（插入排序的一种）：
希尔排序是插入排序的升级版，其升级之处在于分组排序，分组移动插入。插入排序每个元素都需要与之前所有的元素进行比较等操作，但希尔排序却是跳跃式的操作，只有最后一次遍历才是对之前所有元素进行操作。由于每次都要进行分组，所以有可能两个相同的数的相对位置会发生改变，所以希尔排序是不稳定的
具体看图：
以下示例为一组无需数组，假设这里的分组间隔为（length/2）即：gap=4
分组间隙为4，即从gap开始往后每一元素下标减去gap对应的元素，这些为一组进行比较，每一次比较前保存当前值和索引，与当前索引和gap的差对应的元素进行比较。（注：0，4，8位置应该为一组，不小心忘画了）
分组间隔为4，索引0、4、8为一组进行元素比较，第一轮结束。
gap=gap/2=2，即分组间隔为2
后面的操作与第一轮一样。图示过程如下：
最后一轮，也就是gap=gap/2=1。这里只列出了变化了的操作。
具体代码描述：
1 public static void shellSort(int[] nums) {
2 for (int gap = nums.length / 2; gap > 0; gap /= 2) {// 间隙间隔减半
3 for (int i = gap; i < nums.length; i++) {// 从gap开始遍历到数组尾部
4 int j = i;// 当前索引复制给j为从当前i到之前所有的j-gap
5 int temp = nums[j];// 保存当前待插入的值
6 while (j - gap >= 0 && temp < nums[j - gap]) {// 同一间隔组从后往前进行比较，并且当索引值j-gap<0时就表示这一组已排序完成
7 nums[j] = nums[j - gap];// 元素后移
8 j -= gap;// 进行下一个组内比较，j等于组内前一个元素的索引
9 }
10 nums[j] = temp;// 将待插入的值放到
11 //System.out.println(Arrays.toString(nums));
12 }
13 }
14 }
测试：
// before:20:36:38:324
// after: 20:36:41:82
// 800w数据(数据小于1000w)排序：花了大概3s
由此可见，希尔排序很大程度上提高了插入排序的性能！
最坏时间复杂度：O(nlog2n) 空间复杂度：O(1) 不稳定