我不明白为什么希尔排序效率更高。 所以根据我的理解，这是两种算法的比较：
插入排序：O(n^2)，因为我们首先遍历整个数组（有点将其划分为已排序的子数组），然后内循环插入新元素（该元素不包含在已排序的子数组中） 希尔排序：与插入完全一样，但需要进行一些预先工作。（使其几乎排序）然后使用插入。 所以shell基本上就是Pro-work+Insertion。虽然我知道前期工作会减少交换，但无论如何我们都需要在间隙 = 1 时遍历每个元素。 那么为什么它有用呢？
插入排序：O(n^2)，因为我们首先遍历整个数组（有点将其划分为已排序的子数组）
不是“进入已排序的子数组”，而是进入one排序的前缀和未排序的余数。
希尔排序：与插入完全一样，但需要进行一些预先工作。（使其几乎排序）然后使用插入。所以shell基本上就是Pro-work+Insertion。
前期工作可以理解为插入排序的执行，但是在数组的子序列上，其中定义该子序列的索引相距固定距离。
虽然我知道前期工作会减少交换，但无论如何我们都需要在间隙 = 1 时遍历每个元素。那么为什么它有用呢？
就像你说的，前几轮（差距> 1）将使几个值更接近最终目的地，因此最后一轮需要更少的交换。
输入：[4,3,2,1]
使用标准插入排序，我们需要（相当于）三次交换才能将最小值 (1) 放入其最终位置。
如果我们应用第一个间隙为 2 的希尔排序，那么这意味着我们对子序列 [4, 2] 和子序列 [3, 1] 进行插入排序
这两个插入排序导致两次交换和这个数组：
[2,1,4,3]
现在可以确定数组的最小值要么位于索引 0，要么位于索引 1。因此，要在其最终位置获得最小值，最多需要一次交换的成本。这显示了一个收益：我们只需要两次交换即可获得最低值。
在希尔排序的“预工作”中执行的交换平均而言将使值更接近其目标位置，其成本低于使用普通插入排序将它们移动到目的地的成本，因为后者只能交换相邻元素。之前的几轮比赛并不总能为他们的最终位置带来价值，但平均而言，它们会让他们更接近最终位置。最后一轮要做的工作预计会比仅使用插入排序将每个值从其原始位置移动的情况要少得多。