编程知识分享
一个 Gap 带来的改变：重新拆解我曾经看不懂的希尔排序
作者：零点命运
一个 Gap 带来的改变：重新拆解我曾经看不懂的希尔排序
希尔排序gif
引言
想必学过编程，或者对编程稍微有些兴趣的人，都或多或少见过这张图。
这就是著名的希尔排序（Shell Sort）。
记得刚学会冒泡排序、选择排序和插入排序的时候，我第一次看到希尔排序的代码，盯着看了半天，却始终没想明白它到底是怎么把数组排好序的。
明明看起来只是多了一个 gap，为什么整个排序过程就突然变得不一样了？
后来随着接触的东西越来越多，这个问题也一直被我放在了记忆的某个角落里。偶尔想起，却始终没有真正停下来把它弄明白。
直到昨晚，我又一次看到了希尔排序。
突然觉得，既然以前没搞懂，那这次就花点时间认真看看。
于是今天抽了点时间，从代码重新开始，一点一点地把这个曾经让我困惑了很久的排序算法拆开来看。
这一次，我终于开始理解它到底在做什么了。
介绍
首先，希尔排序（Shell Sort）的希尔是怎么来的，其实是因为创作者叫唐纳德·希尔（Donald Shell）。
其次，希尔排序是怎么实现的？如下：
public static void shellSort(int[] arr) {
int n = arr.length;
for (int gap = n / 2; gap > 0; gap /= 2) {
for (int i = gap; i < n; i++) {
int temp = arr[i];
int j = i;
while (j >= gap && arr[j - gap] > temp) {
arr[j] = arr[j - gap];
j -= gap;
}
arr[j] = temp;
}
}
}代码没多少，看着有点复杂，双重for循环内嵌套一个while循环。
解释其之前我想从个故事说起：
假如你是一个苹果排序员，你的任务是将一排排大小排列不一的苹果重新排列成一排排从左到右从小到大的苹果，你走到一排苹果前，拿起最左边的苹果挨个对比，放下小的，留下最大，最后将最大的放在最后，然后回到最左边，找到第二大的，这时你知道最后一个是最大的不用比较，放在了倒数第二位，再回到最左边，就这样循环，排序就完成了，这就是冒泡排序。
然后你把这种方法交给机器人，机器人按你的方法一排排过去排序。过了一会你发现，如果一排苹果本来就是从左到右从小到大的，机器人还是会从头到尾执行一遍，你就想如果苹果本来就是从小到大的就不要一一比较了，从左到右当出现更小的再向左去比较，左边遇到更小的放在其右边或没有更小的放到最左边，然后回到之前的位置继续比较，这就是插入排序。
但你发现如果苹果从左到右是从大到小的，得将最大的慢慢推到最后，消耗的时间还是和之前一样。
然后你想到左边最大的苹果得一步一步往前推，能不能直接推到最后去呢。
所以能不能先将苹果大跨度对比简单排序一下，最后再来一次插入排序，不就可以解决最大的在最左边的问题了吗，这就是当时希尔的想法，但具体怎么大跨度对比简单排序，来看一下希尔排序是怎么去解决的。
先来对比看一下插入排序的代码:
public static void insertionSort(int[] arr) {
int n = arr.length;
for (int i = 1; i < n; i++) {
int key = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > key) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = key;
}
}你会发现和希尔排序第一层for循环的内部很像，但又略有不同，你可以将其大致理解为，把插入排序逐渐贯彻到底，插入排序是将一个位置与下一个位置对比，就是n与n+1，但如果把这两个位置的距离逐渐拉大，就可以更快的将更早出现的大数移动到更后面去，但第一次的距离多大合适呢，希尔就想到使用二分法，跨度就是数组长度的一半，将前排数组与后排数组一对一比较，大的放后面，再继续二分，跨度就是之前的一半，前排、后排一对一比较，一直分直到跨度为一，最后就进行了一次插入排序。
下面是具体通过代码的解读：
第一个 for：决定 Gap
第一个
for 循环实际上是在不断缩小 Gap。如果数组长度为 8，那么 Gap 的变化就是：
8 / 2 = 44 / 2 = 22 / 2 = 11 / 2 = 0所以整个排序会经历三个阶段：
Gap = 4Gap = 2Gap = 1这里的 Gap 可以理解成两个元素之间的比较跨度。
所以第一个
for 做的事情可以简单理解成：决定这一轮排序中，元素之间要隔多远进行比较。
第二个 for：遍历当前 Gap 后面的元素
当
Gap = 4 时：for (int i = gap; i < arr.length; i++)也就是：
i = 4i = 5i = 6i = 7因此第一次遍历的就是数组下标
4 ~ 7 的元素。如果使用下标来表示，那么第一次比较关系就是：
arr[4] ↔ arr[0]arr[5] ↔ arr[1]arr[6] ↔ arr[2]arr[7] ↔ arr[3]也就是说，当前元素会和它前面 Gap 个位置的元素进行比较。
比如：
[ 8, 3, 7, 4, 2, 6, 5, 1 ]arr[0]-arr[4]Gap = 4此时比较：
8 和 2
如果左边的
8 比当前的 2 大，那么 8 就应该向后移动。while：寻找当前元素真正应该插入的位置
这里是我一开始比较容易误解的地方。
while 并不是简单地「比较一次，然后交换两个元素」。实际上，它执行的是一次 Gap 插入排序。
例如：
int temp = arr[i];int j = i;这里的
temp 保存了当前准备插入的元素。假设：
temp = 2而它前面的元素是：
8因为：
8 > 2所以执行：
arr[j] = arr[j - gap];实际上是把
8 向后移动：[ 8, 3, 7, 4, 2, 6, 5, 1 ]↓[ 8, 3, 7, 4, 8, 6, 5, 1 ]此时
2 并没有消失。它被暂时保存在：
temp变量中。
然后：
j -= gap;继续向前寻找。
如果前面的元素仍然比
temp 大，就继续移动。例如 Gap = 2 时，假设某个元素需要沿着下面这条序列寻找位置：
arr[0]↓arr[2]↓arr[4]↓arr[6]如果当前元素比较小，就可能出现：
9 → 7 → 5 → 1当前的
1 会依次和：5 7 9进行比较。
每发现一个更大的元素，就向后移动一个 Gap。
最后：
arr[j] = temp;把最开始保存的
1 放入最终找到的位置。所以
while 真正做的事情是：不断把比
temp 大的元素向后移动，直到找到一个不比 temp 大的位置，然后把 temp 插进去。这和普通插入排序的思想其实是一样的。
区别只在于：
普通插入排序
希尔排序
Gap = 1希尔排序
Gap = 4Gap = 2Gap = 1为什么第一轮 Gap = 4 时，while 好像没什么作用？
这是我在理解代码时觉得比较有意思的一个地方。
当数组长度为 8，第一轮
Gap = 4 时：arr[0] ↔ arr[4]arr[1] ↔ arr[5]arr[2] ↔ arr[6]arr[3] ↔ arr[7]因为 Gap 已经是数组长度的一半，所以每个元素在当前阶段最多只能向前跨越一次。
因此这一轮中，
while 通常最多执行一次。但到了下一轮：
Gap = 2情况就发生变化了。
这时候元素可以沿着：
0 → 2 → 4 → 6或者：
1 → 3 → 5 → 7不断向前寻找。
于是
while 就可能执行多次。再到：
Gap = 1就变成了普通的插入排序：
0 → 1 → 2 → 3 → 4 → 5 → 6 → 7此时整个数组已经经过前面两轮 Gap 的整理，已经比最开始更加接近有序。
所以最后一次插入排序不需要再面对一个完全混乱的数组。
这也是希尔排序最核心的思想：
先用较大的 Gap，让元素进行远距离移动，快速消除一些距离很远的逆序关系。
再逐渐缩小 Gap，让数组越来越接近有序。
最后 Gap = 1，使用插入排序完成最后的整理。
我现在对希尔排序的理解
如果把整个过程压缩成一句话，我现在更倾向于这样理解：
Gap = 4
粗略整理
↓
Gap = 2
进一步整理
↓
Gap = 1
精细整理
粗略整理
↓
Gap = 2
进一步整理
↓
Gap = 1
精细整理
所以希尔排序并不是简单地把插入排序改成了隔几个位置比较。
它真正有意思的地方在于：
先通过大跨度的移动，让数组变得接近有序，再利用插入排序擅长处理近乎有序数据的特点，完成最后的排序。
也就是说，希尔排序的核心是让插入排序变得更容易。