简介

希尔排序，也称递减增量排序算法，是插入排序的一种更高效的改进版本。但希尔排序是非稳定排序算法。

希尔排序是基于插入排序的以下两点性质而提出改进方法的：

插入排序在对几乎已经排好序的数据操作时，效率高，即可以达到线性排序的效率；
但插入排序一般来说是低效的，因为插入排序每次只能将数据移动一位；

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行依次直接插入排序。

算法步骤

选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1(最后一个必然是1)；
按增量序列个数 k，对序列进行 k 趟排序；

每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

代码实现

public static int[] sort(int[] sourceArray) {
     int[] list = Arrays.copyOf(sourceArray, sourceArray.length);
     //定义一个增量序列gap 下面是目前常用的增量间隔
     int gap = 1;
     while (gap < list.length/3){
         gap = gap * 3 + 1;
     }
     while (gap>0){
         //从第gap个开始 每次往前前进一步
         for (int i = gap; i < list.length;i++) {
             //下面就是类似插入排序的操作
             int temp = list[i];
             //判断的是每隔gap个的数字的大小
             int j = i-gap;
             //如果当前的数小于gap之前个数字的话 进入循环
             while (j >= 0 && temp < list[j]) {
                 //后一个数 = 前一个数
                 list[j+gap] = list[j];
                 j -= gap;
             }
             //单次循环结束 如果j的位置发生变化的话 就让变化后的位置=temp 如果没变化 即等于原来的数字 做个判断 10万个数字排序可以节省大概30%的时间
             if (j!=i-gap){
                 list[j+gap] = temp;
             }
         }
         //gap=原来的3分之一 进入下一个循环
         gap = (int) Math.floor(gap/3);
     }
     return list;
 }

图解

(有点简陋.. 可能只有自己看得懂了)

每次循环后小的数字就会被换到前面数组就变得更加的有序因为插入排序面对有序数组的排序时间是接近线性阶的越有序就越快下次循环的时候碰到这个数字就可以更快的执行插入排序从而达到希尔排序 - 图2

好于平方阶的时间复杂度

疑点

代码第23行别人写的代码都没有进行判断但是加了判断排序正常并且节省了时间不知道会不会有问题