希尔排序(Shell's Sort)是插入排序的一种又称“缩小增量排序”（Diminishing Increment Sort），是直接插入排序算法的一种更高效的改进版本。希尔排序是非稳定排序算法。该方法因D.L.Shell于1959年提出而得名。

希尔排序是把记录按下标的一定增量分组，对每组使用直接插入排序算法排序；随着增量逐渐减少，每组包含的关键词越来越多，当增量减至1时，整个文件恰被分成一组，算法便终止。 [1]

算法步骤

• 选择一个增量序列 t1，t2，……，tk，其中 ti > tj, tk = 1；
• 按增量序列个数 k，对序列进行 k 趟排序；
• 每趟排序，根据对应的增量 ti，将待排序列分割成若干长度为 m 的子序列，分别对各子表进行直接插入排序。仅增量因子为 1 时，整个序列作为一个表来处理，表长度即为整个序列的长度。

参考代码

public static void main(String[] args) {
 int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
 int gap = 1;
 while (gap < arr.length) {
 gap = gap * 3 + 1;
 }
 while (gap > 0) {
 for (int i = gap; i < arr.length; i++) {
 int tmp = arr[i];
 int j = i - gap;
 while (j >= 0 && arr[j] > tmp) {
 arr[j + gap] = arr[j];
 j -= gap;
 }
 arr[j + gap] = tmp;
 }
 gap = (int) Math.floor(gap / 3);
 }
 //输出结果
 for (int i : arr) {
 System.out.print(i + " ");
 }
 //0 1 2 3 4 5 6 7 8 9
 //Process finished with exit code 0
}