🔍什么是希尔排序
希尔排序（Shell Sort）是插入排序的一种高效率的改进版本，也称为缩小增量排序。它基于插入排序，但使用了不同的增量序列，通过将序列分成若干个子序列进行插入排序，逐步减小增量，最终完成排序。
希尔排序法的基本思想是：先选定一个整数，把待排序的数据所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。 每次排序让数组接近有序的过程叫做预排序，最后一次等于1时插入是直接插入排序。
🔑希尔排序分组思想
1.我们首先从间隔为5分组，间隔为gap分为一组，总计gap组，多组并排
gap代表间隔，此时为我们已经分好组了
第一组： 9 4
第二组： 1 8
第三组： 2 6
第四组： 5 3
第五组： 7 5
我们对这几组分别进行排序分别得到:
2.我们缩小gap增量,使的变成2
此时为我们分组是
第一组： 4 2 5 8 5
第二组： 1 3 9 6 7
我们对这两组分别进行排序分别得到:
3.缩小gap增量,使的变成1,变成1就是已经变成插入排序了。到这里已经是最后一步了。
gap >1 就是预排序
gap越大，大的数可以更快的到后面，小的数可以更快的到前 越不接近有序
gap越小，大的小的挪动越慢，但是他越接近有序
gap会逐渐缩小，间隔也会逐渐缩小。
整体的数据会更加趋于有序，这个时候使用直接插入排序效率会更高。
gap == 1，就是直接插入排序
📈希尔排序的优缺点
希尔排序是基于插入排序的一种排序算法，它通过将一串待排序的数据分成多个子序列来实现排序，最终将这些子序列合并成一个有序序列。相比插入排序，希尔排序的优缺点如下：
- 优点
1.相对于其他简单的排序算法（如冒泡排序、选择排序等），希尔排序的时间复杂度较低，尤其是对于大规模数据的排序。
2.希尔排序是一种原地排序算法，不需要额外的存储空间。
3.由于希尔排序改变了插入排序中元素的位置，从而减少了元素之间的比较和交换次数，因此希尔排序在实际应用中展现出了较高的排序效率。
- 缺点
1.希尔排序的时间复杂度与增量(gap)序列有关，不同的增量(gap)序列会影响排序的效率。
2.希尔排序是一种不稳定的排序算法，相同的元素在排序后可能会改变相对位置。
👨💻希尔排序代码剖析
- 确定增量序列gap
1.先把gap给成数组的长度int gap = n
2.确定 增量序列gapgap=gap/3+1 +1可以保证最后一次一定是1 即最后一次是直接插入排序
- 确定循环条件外层循环条件
while (gap > 1)该while循环的作用是随着跨度gap的不断减小，进行希尔排序的每一轮迭代，直到跨度为1时结束循环，完成希尔排序。
- 确定循环控制每组数据进行插入排序的过程
for (int i = 0; i < n - gap; ++i) n - gap表示数组a中第一组数据的最后一个元素下标。在希尔排序中，我们将数组n个元素分成若干组（组与组之间的元素下标相差gap），每组中的元素个数通常为gap。因此，在对每组数据进行插入排序时，需要在第一组数据中从第一个元素开始进行比较，直到最后一个元素。由于每组数据中的元素下标相差gap，所以第一组数据的最后一个元素下标为n-gap。因此，for循环的条件判断语句可以写为 i < n - gap。
- 使用两个变量确定当前组需要排序的范围和下一个待插入的元素。
int end = i
int tmp = a[end + gap]
- 里层循环不断向后更新位置
(end >= 0)不断查找当前元素 a[end] 在以 end-gap 为结尾的子序列中的正确位置，并将其插入到正确的位置中，直到 end 的值小于 0 为止
- 判断 元素是否比待插入元素 tmp 大
if (a[end] > tmp)
{
a[end + gap] = a[end]
end-=gap 需要往后移动一个 gap 的位置，以便为下一个待插入元素腾出位置
}
- 实现待插入操作
a[end + gap] = tmp 在这之前，我们通过 a[end + gap] = a[end]; 操作，已经将子序列中所有大于待插入元素的元素往后移动了一个 gap 的位置，以腾出正确的插入位置。现在，我们已经找到了待插入元素的正确位置，也就是以 end-gap 为结尾的子序列中的某个位置。因此，直接将待插入元素(tmp)赋值给 a[end+gap]，实现了在子序列中插入待插入元素的目的。
void ShellSort(int* a, int n) { int gap = n; while (gap > 1) // 当跨度为1时，就是普通的插入排序，不需要再进行希尔排序了 { // 通过除以3再加1的方式来缩小跨度 +1可以保证最后一次一定是1， //这是希尔排序中常用的增量序列 gap = gap / 3 + 1; for (int i = 0; i < n - gap; ++i) // 对每组数据进行插入排序 { int end = i; // end表示每组数据的最后一个元素的下标 int tmp = a[end + gap]; // tmp表示当前组中下一个待插入的元素 while (end >= 0) // 在当前组中，从后往前找到tmp应该插入的位置 { if (a[end] > tmp) // 如果当前位置的元素比tmp大，就将该元素后移gap个位置，为tmp腾出位置 { a[end + gap] = a[end]; end -= gap; // 继续向前查找 } else // 如果当前位置的元素比tmp小，就找到了tmp应该插入的位置 { break; } } a[end + gap] = tmp; // 将tmp插入到当前组的合适位置 } } }
在上面的代码中，我们可以看到，希尔排序主要包含两个阶段：预排序阶段和插入排序阶段。其中，预排序阶段是通过不断缩小跨度来实现的，而插入排序阶段则是对每组数据进行插入排序。在预排序阶段中，我们使用了一个常用的增量序列： gap=gap/3+1，这个增量序列可以保证最后一次的跨度一定是1，从而保证了最后一次排序是普通的插入排序。
在插入排序阶段中，我们首先定义了一个变量end，表示每组数据的最后一个元素的下标。然后，我们将当前组中下一个待插入的元素存储在了tmp变量中。接着，我们从后往前遍历当前组中的元素，将比tmp大的元素后移gap个位置，为tmp腾出位置。最后，我们将tmp插入到当前组的合适位置。
