希尔排序（Shell Sort）是一种插入排序算法，因D.L.Shell于1959年提出而得名。
Shell排序又称作缩小增量排序。
1、算法思想
先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插入排序；然后，取第二个增量d21重复上述的分组和排序，直至所取的增量d t=1(d tt-l<… 21)，即所有记录放在同一组中进行直接插入排序为止。
该方法实质上是一种分组插入方法。
2、代码实现
package sort;
/**
* 希尔排序ShellSoet
*
* 先取一个小于n的整数d1作为第一个增量，把文件的全部记录分成d1个组。
*
* 所有距离为dl的倍数的记录放在同一个组中。先在各组内进行直接插人排序；
*
* 然后，取第二个增量d21重复上述的分组和排序，直至所取的增量d t=1(d tt-l<… 21)，即所有记录放在同一组中进行直接插入排序为止。
*
* 该方法实质上是一种分组插入方法。
*
* @author yunhai
*/
public class ShellSort {
public static void main(String[] args) {
int source[] = new int[]{49, 38, 65, 97, 76, 13, 27, 49, 55, 4, 6};
System.out.print("排序前：\t");
printArray(source);
shellSort(source);
System.out.print("排序后：\t");
printArray(source);
}
private static void shellSort(int[] source) {
int j;
for (int gap = source.length / 2; gap > 0; gap /= 2) { // gap 为增长序列，递减至1【亦可自定义增长序列】
for (int i = gap; i < source.length; i++) { // 【直接插入排序】，从第一个gap处向后移,直至移到最后一个数
int temp = source[i];// 当前gap处的值
for (j = i; j >= gap && temp < source[j - gap];) {// 最后一个数如果是第一个gap的倍数，按理应第一次循环，但却最后循环
source[j] = source[j - gap]; // 较大数往后移
j -= gap; // 亦可放在循环体内
}
source[j] = temp; // 跳出循环意味着temp的位置已确定
}
System.out.print("增长序列" + gap + ": ");
printArray(source);
}
}
private static void printArray(int[] source) {
for (int i = 0; i < source.length; i++) {
System.out.print(source[i] + ",");
}
System.out.println();
}
}
3、算法分析
1）、增量序列的选择。
Shell排序的执行时间依赖于增量序列。好的增量序列的共同特征如下：
a.最后一个增量必须为1。
b.应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
有人通过大量实验给出了目前最好的结果：当n较大时，比较和移动的次数大概在n^1.25到n^1.26之间。
2）、Shell排序的时间性能优于直接插入排序。
希尔排序的时间性能优于直接排序的原因如下：
a.当文件初态基本有序时，直接插入排序所需的比较和移动次数均较少。
b.当n值较小时，n和n^2的差别也较小，即直接插入排序的最好时间复杂度O(n)和最坏时间复杂度O(n^2)差别不大。
c.在希尔排序开始时增量较大，分组较多，每组记录数目少，故每组内直接插入排序较快，后来增量d(i)逐渐缩小，分组数逐渐减少，而各组的记录数目逐渐增多，但由于已经按d(i-1)做为距离拍过序，使文件较接近于有序状态，所以新的一趟排序过程也较快。因此，希尔排序在效率上较直接插入排序有较大的改进。
3）、稳定性
希尔排序是不稳定的。
4、算法改进
增量序列的选择：Shell排序的执行时间依赖于增量序列。
好的增量序列的共同特征：
① 最后一个增量必须为1；
② 应该尽量避免序列中的值(尤其是相邻的值)互为倍数的情况。
源码地址：https://github.com/zxiaofan/Algorithm/blob/master/src/sort/ShellSort.java