shell 排序是一种插入排序
亦被称为 缩小增量排序
shell排序的实质就是分组插入排序
基本思想
- 将需要排序的元素序列array分割成若干个子序列(array1,array2,array3......)
是根据“增量”分成的子序列，增量要比array.length小，尽量可以被array的长度整除(默认增量gap=array.length/2) - 对子序列分别进行直接插入排序
- 然后依次缩小增量(gap=gap/2)进行重新划分子序列，对划分好的子序列重新进行排序
- 最终循环2-3步骤，直到gap=1，进行完最后一次排序，排序终止
描述起来不难，希尔排序背后的逻辑却是不简单，希尔排序是希尔（Donald Shell）于1959年提出的一种排序算法，属于最早的一批突破复杂度的一批次排序，其复杂度受着数组本身的排列和初始gap的取值有关，对于其复杂度的计算/证明，对我个人而言有些难，数学战五渣，只能哭唧唧，有能力的大佬们可以看一下本链接：https://blog.csdn.net/u013007900/article/details/51232472
下面笔者本着实践的原则，进行一下希尔排序的图解及实现：
首先，笔者认为前面文字还是过于抽象，并不能直观的表达增量(也称希尔增量)的含义，在此结合图形解释一下gap究竟是怎么将数组分组的，如下图：
如上图所示，数组的长度为9，初始gap指定为4，即按照增量=4来进行数组分组；
数组下方标记了其元素对应的index索引序号，按照gap进行递增，构造对应分组：
第一组：index=0,4,8 → {array[0], array[4], array[8]}
第二组：index=1,5 → {array[1], array[5]}
第三组：index=2,6 → {array[2], array[6]}
第四组：index=3,7 → {array[3], array[7]}
上图已经足够表明了如何进行分组，下面就开始进行图解整个排序的流程，如下图：
上图中，按照之前所描述的算法逻辑：
- gap依次取值 4, 2, 1，即总共进行了三轮的分组排序；
- 每轮的分组数量分别为 4组, 2组, 1组（可根据图中颜色进行区分组数）
- 每轮仅对各自组内的序列进行排序即可。
按照算法给定的是对分组进行直接插入排序，个人认为只要能对组内元素进行排序，什么算法均可
原理讲的差不多了，下面直接上代码，将理论具现到实践中：
public void shellSort(int[] arrays) {
// 缩小增量法
int gap = arrays.length / 2;
while (gap >= 1) {
// 共有gap组通过增量的分组，进行排序
for (int i = 0; i < gap; i++) {
// 对增量对应一组的数组进行排序(对子数组随便选择一个排序算法)
for (int j = i + gap; j < arrays.length; j += gap) {
//i,i+gap,i+2*gap,i+3*gap...
int index = j;
while (index >= i + gap && arrays[index] < arrays[index - gap]) {
swap(arrays, index, index - gap);
index -= gap;
}
}
}
gap /= 2;
}
}
希尔排序，总的来说不难理解，最终其实也是对gap=1，即整个数组进行最终的直接插入排序，但之前的几轮排序确定了各自分组内的相对位置，对最终的增量gap=1的排序其实是起到了辅助作用。
至于具体的证明其比直接插入复杂度低，性能更高，从书面语我可能给不出什么解释，想了解的还是戳上面给出的链接吧，在这里也再贴一下：https://blog.csdn.net/u013007900/article/details/51232472
