希尔排序就是对插入排序的一种优化
希尔排序将固定的数组分组，每个小组进行插入排序，每个小组插入排序之后继续分组直到最后是一个1个整体，因为每次插入排序都会式数组固定有序
可以大大优化最后的时间
举个例子 现在有10个小学生{1, 5, 2, 6, 7, 3, 4, 8,9,10}
先将小学生分为arr.length/2=5组 也就是索引0和5对应 1和6对应 2和7对应等等
每个小组内先进行插入排序（也就是索引0和5比较是否交换 1和6比较是否交换等等） 第一次排序之后应该为{1,4,2,6,7,3,5,8,9,10}
接着再将小组分组 5/2=2 将小组分为2组 每组5个 这次是0和2对应 1和3对应
现在被分为两组[1,2,7,5,9]和[4,6,3,8,10]
再进行交换 排序之后应该为{1,3,2,4,5,4,7,8,9,10}
最后再进行分组2/2=1 当变量为1的时候也就是最后一次分组了 因为每次分组排序都进行过插入排序 所以数组是部分有序的
代码：
public static void compare3(int[] arr) { int gap = arr.length / 2;//4 while (gap >= 1) { for (int i = gap; i < arr.length; i++) { int current = arr[i]; int perIndex = i - gap; while (perIndex >= 0 && current < arr[perIndex]) { //当前数字比前面的小，需要将前面的数字赋值给当前数字 arr[perIndex + gap] = arr[perIndex]; perIndex = perIndex - gap; } arr[perIndex + gap] = current; } gap = gap / 2; } for (int i = 0; i < arr.length; i++) { System.out.println(arr[i]); } }
原文：https://www.cnblogs.com/Vinlen/p/12896152.html