我要评论目录
一、引言
二、基本原理
三、实现步骤
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;//满足大小关系后插入到指定位置
}
}
}
七、应用场景
发表评论