思路
希尔排序，与其他排序不同的是，别的排序都能通过名字关联上，而希尔排序的名字，怎么看也不太像中文。
其实希尔排序就是插入排序的进化版，它会先声明一个间隙参数，然后按照间隙参数，把数组分成若干各子数组，对子数组进行插入排序。随着间隙越缩越小，整个数组的顺序也就慢慢排好了。
看起来不太容易理解，下面就拆开说一下步骤：
- 计算出一个间隙值；
- 按照间隙值把数组分成若干个子数组；
- 对子数组进行插入排序；
- 将间隙缩小，重新分组并插入排序；
- 直至整个数组排序完成。
讲解
有数组如下：
image.png
现在要对它进行希尔排序。首先计算出一个间隙值gap，我们用数组长度除以2，计算出第一个gap：8 / 2 = 4；
那么间隔为4（比如下标为0的元素，加4，即下标为4的元素，两个元素看做一个子数组）的元素即为一个子数组，我们用不同颜色将子数组标记出来：
image.png
然后对子数组进行插入排序，插入排序前面的文章讲过了，这里就直接进行排序了：
image.png
然后将gap值自除2，计算出下一个gap为：4 / 2 = 2，并将数组重新拆分子数组：
image.png
这次就分成了两个子数组，继续对这两个子数组进行排序：
image.png
顺序越来越明显了。gap再次自除2，计算出最后一个gap为：2 / 2 = 1，那么这次拆分出来的数组其实就是一个完整的数组了：
image.png
再次对数组进行排序：
image.png
整个数组的顺序就拍好啦，这就是希尔排序。
实现
@Test
public void shellSort() {
int[] nums = new int[]{26, -3, 14, -15, 0, 324, 1, 22};
sort(nums);
System.out.println(Arrays.toString(nums));
}
private void sort(int[] nums) {
// 如果数组长度小于2则不需要排序
if (nums.length < 2) {
return;
}
// 计算出第一个间隙值
int gap = nums.length / 2;
// 当gap值自除到0时，说明已经完成排序，结束遍历
while (gap != 0) {
// 子数组个数，每个子数组都要排序，所以也是要遍历的次数
for (int times = 0; times < nums.length / gap; times++) {
// 进行插入排序，因为相邻元素变成了间隙为gap，所以单位都是gap
for (int i = times + gap; i < nums.length; i += gap) {
int cur = nums[i];
int insertIndex = -1;
for (int j = i - gap; j >= 0; j -= gap) {
if (nums[j] > cur) {
nums[j + gap] = nums[j];
insertIndex = j;
}
}
if (insertIndex != -1) {
nums[insertIndex] = cur;
}
}
}
// gap自除2
gap /= 2;
}
}
image.png
