【数据结构与算法】希尔排序：基于插入排序的高效排序算法

            💓 博客主页：倔强的石头的CSDN主页 

           📝Gitee主页：倔强的石头的gitee主页

            ⏩ 文章专栏：《数据结构与算法》

                                  期待您的关注

​

目录

一、引言 

二、基本原理

三、实现步骤

四、C语言实现

五、性能分析

1. 时间复杂度：近似为O(Nlog2N)

2. 空间复杂度：O(1)

3. 稳定性：不稳定的

六、优化

七、应用场景

---

一、引言 

希尔排序（Shell Sort）是插入排序的一种更高效的改进版本，也称为缩小增量排序。

希尔排序由Donald Shell于1959年提出，并在其发表的论文“A high-speed sorting procedure”中详细描述了该算法。希尔排序的直接灵感来源于插入排序，但它在插入排序的基础上进行了显著的改进，旨在提高排序效率，特别是针对大规模数据集。

想要读懂希尔排序，最好先理解插入排序，参考下面这篇文章

【数据结构与算法】深入解析插入排序算法：原理、实现与优化-CSDN博客

二、基本原理

希尔排序的基本思想是：先将整个待排序的记录序列分割成为若干子序列分别进行直接插入排序，待整个序列中的记录“基本有序”时，再对全体记录进行一次标准的直接插入排序。

这里的“基本有序”是指：待排序的数组元素值满足某个增量序列的“局部有序”，即对于某个变量gap，序列中所有距离为gap的元素之间是有序的。随着变量gap的逐渐减小，当gap减小到1时，整个序列恰好被“基本有序”，此时再对全体元素进行一次直接插入排序即可

三、实现步骤

 
1.外循环进行多轮预排序
选择一个变量序列：

这个序列是逐渐减小的，gap的值较大时，数据可以更快的前后变动，但不容易"基本有序"；gap较小时数据前后变动较慢，但更接近"基本有序"。  通常可以选取gap = n/3, gap = gap/3, ...，直到gap= 1。

但是要注意，如果直接每次都/3，可能面临的情况就是最后一组gap的值跳过了1，比如n=8时，gap第一次等于2，第二次等于0，解决方法也很简单，gap每次不是/3，而是gap=gap/3+1，就可以让gap最后一次一定会减小到1

2.第二层循环，每一轮预排序中进行分组
按gap进行分组：根据当前的变量gap，将待排序的数组元素下标按gap分组，总共可以分成gap组。比如gap为3时，每一组元素的首元素分别是0，1，2

3.第三层循环，分组之后，控制组里数据执行插入排序
每一组的数据有n/gap个，下标为0，gap, 2gap, 3gap,...的元素分为一组；下标为1，gap+1，2gap+1，3gap+1……的元素分为一组……

这一层循环一个需要注意的细节就是预防数组的越界:每一组分组数据的最后一个数据一般不会是数组的最后一个数据。每次选取的要插入的数据下标是end+gap，那么这个下标不能超过n-gap。比如数组有10个元素，gap为3，第一组数据最后一个数据的下标是9，要保证这一组数据访问到下标9之后，不再向后访问，因为下一次访问end为9，要插入的数据，9+gap的位置已经没有数据了。

4.第四层循环，实现插入排序的过程
每个数据向前扫描和移动，找到合适的位置后插入，直接在插入排序代码的基础上稍加修改即可

5.递减变量gap并重复上述分组排序过程：

每完成一轮按变量gap的分组排序后，将变量gap减小，然后重复分组排序过程，直到变量gap为1，此时整个数组恰好被分成一组，进行最后一次直接插入排序。
 

四、C语言实现

void ShellSort1(int* a, int n)//希尔排序升序
{int gap = n;while (gap > 1)//多组预排序，最后一组gap==1为直接插入排序{gap = gap / 3 + 1;for (int i = 0; i <gap; i++)//控制分组的组数：gap组{for (int j = i; j < n - gap; j += gap)//控制每组的插入元素个数：n/gap个{int key = a[j+gap];int end = j;while (end >= 0 && a[end] > key)//比较和移动元素{a[end + gap] = a[end];end -= gap;}a[end + gap] = key;//满足大小关系后插入到指定位置}}}
}void ShellSort2(int* a, int n)//希尔排序降序
{int gap = n;while (gap > 1)//多组预排序，最后一组gap==1为直接插入排序{gap = gap / 3 + 1;for (int i = 0; i < gap; i++)//控制分组的组数：gap组{for (int j = i; j < n - gap; j += gap)//控制每组的插入元素个数：n/gap个{int key = a[j + gap];int end = j;while (end >= 0 && a[end] < key)//比较和移动元素{a[end + gap] = a[end];end -= gap;}a[end + gap] = key;//满足大小关系后插入到指定位置}}}
}

五、性能分析

1. 时间复杂度：近似为O(Nlog2N)

希尔排序的时间复杂度并不是一个定值，它依赖于增量序列（gap序列）的选取。

• 平均时间复杂度：在多数情况下，希尔排序的平均时间复杂度可以近似为O(Nlog2N)，但这并不是一个严格的结论，因为实际性能会受到增量序列的具体选择和数据初始状态的影响。
• 最佳时间复杂度：在最佳情况下，即数据已经接近有序时，希尔排序可以接近线性排序的效率，但具体数值难以准确给出。
• 最差时间复杂度：在最坏情况下，希尔排序的时间复杂度仍然是O(N^2)。这通常发生在增量序列选择不当，导致算法无法有效减少数据比较和移动次数时。

2. 空间复杂度：O(1)

希尔排序是原地排序算法，它只需要一个额外的空间来存储临时变量（用于数据交换），因此其空间复杂度为O(1)。这意味着希尔排序在排序过程中不会占用额外的存储空间，这对于内存资源有限的环境非常有利。

3. 稳定性：不稳定的

希尔排序是不稳定的排序算法。在排序过程中，由于存在跳跃式的比较和移动，相同元素的相对位置可能会发生变化。因此，在需要保持元素原始顺序的场景中，希尔排序可能不是最佳选择。

六、优化

将第二层第三层循环合为一层循环，
以前是四层循环时，我们是将分组作为一层循环，每组里的数据插入作为一层循环
将两层循环合为一层之后，不是一组一组进行预排序，而是将数据逐个的，与它对应的组里的数据进行预排序，互不影响
优化之后代码更加简洁，但效率没有提升

void ShellSort(int* a, int n)//希尔排序升序代码优化版（效率没有提升）
{int gap = n;while (gap > 1)//多组预排序，最后一组gap==1为直接插入排序{gap = gap / 3 + 1;for (int i = 0; i < n - gap; i++)//控制多组以及插入元素个数{int key = a[i + gap];int end = i;while (end >= 0 && a[end] > key)//比较和移动元素{a[end + gap] = a[end];end -= gap;}a[end + gap] = key;//满足大小关系后插入到指定位置}}
}

七、应用场景

希尔排序（Shell Sort）由于其实现简单且在某些情况下表现良好，因此在一些特定的应用场景中得到了应用。以下是一些希尔排序可能适用的场景：

1. 中等规模数据集：对于小到中等规模的数据集（比如几千个元素），希尔排序通常能够提供良好的性能。在这些情况下，希尔排序可能比更复杂的排序算法（如快速排序、归并排序等）更容易实现且效率相当。

2. 部分有序数据集：如果数据集已经部分有序（即元素接近它们的最终位置），希尔排序可以利用这一点来更快地完成排序。因为希尔排序通过引入间隔（gap）来允许元素在更远的距离上进行交换，这有助于减少数据移动的次数，从而加速排序过程。

3. 内存受限的环境：希尔排序是原地排序算法，只需要O(1)的额外空间。在内存受限的环境中（如嵌入式系统或大型数据集排序时内存使用受到严格控制的场景），这一点尤为重要。

4. 实时系统：在一些实时系统中，排序操作的响应时间非常关键。希尔排序由于其实现简单且通常能够快速完成排序，因此可能是一个不错的选择。尽管在最坏情况下其时间复杂度为O(N^2)，但在实际应用中，它往往能够更快地完成排序，特别是在数据集部分有序或规模适中的情况下。

5. 教育目的：在教学和学习排序算法的过程中，希尔排序是一个很好的例子，因为它展示了如何通过引入简单的改进（即间隔序列）来显著提高基本排序算法（如插入排序）的性能。

然而，需要注意的是，对于非常大的数据集或对数据排序的稳定性有严格要求的应用场景，希尔排序可能不是最佳选择。在这些情况下，可能需要考虑使用更高效的排序算法（如快速排序、归并排序或堆排序）或稳定的排序算法（如归并排序、冒泡排序等）。

总之，希尔排序适用于中等规模、部分有序、内存受限或需要快速响应的实时系统等场景。但在选择排序算法时，还需要根据具体的应用需求和数据集特点进行综合考虑。