希尔排序（C语言实现）
目录
1.希尔排序( 缩小增量排序 )
基本思想：
1.先选定一个小于N的整数gap作为第一增量，然后将所有距离为gap的元素分在同一组，并 对每一组的元素进行直接插入排序。然后再取一个比第一增量小的整数作为第二增量，重 复上述操作…
2.当增量的大小减到1时，就相当于整个序列被分到一组，进行一次直接插入排序，排序完成。
2.动图 
3.代码实现
思路：
预排序实现
插入排序
预排序实现
根据当前增量，数组被分为若干子序列，这些子序列的元素在原数组中间隔着固定的增量。对每个子序列应用插入排序。
假设最初增量为5
d越大，数据挪动得越快；d越小，数据挪动得越慢。前期让d较大，可以让数据更快得移动到自己对应的位置附近，减少挪动次数。
注：一般情况下，取序列的一半作为增量，然后依次减半，直到增量为1（也可自己设置）。
完成了一轮希尔排序，此时整个数组并不完全有序，但是已经比原始的数组更接近有序了。然后减小增量，通常是将原来的增量除以2（或者除以3+1），现在选择下一个增量为 2，按照此排序规则继续预排序即可，直到增量为1时，则为直接插入排序，此时则排序完成。
子序列排列实现
//子序列
int gap;
int end；
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 3] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;这里只需要在插入排序的基础上修改一下即可。end的所加所减都为gap;
单趟排序实现
int gap;
//单趟排序实现
for (int i = 0; i < n - gap; i += gap)
{
//子序列
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 3] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}这里的 n-gap 和插入排序中的 n-1 一样是为了防止越界
对整组数进行子排序
int gap;
for (int j = 0; j < gap; j++)
{
//单趟排序实现
for (int i = 0; i < n - gap; i += gap)
{
//子序列
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + 3] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}外层循环
（for (int j = 0; j < gap; j++)）意在对每个以gap为间隔的分组进行遍历。
这里进行一下优化：
三层代码的循环是每一组子排序排完再进行下一组，直到排完整个数组。
下面这组代码优化后效率并没有很大的提升，只是代码更为简洁。
这组代码是齐头并进，排完第一组的前n个就排下一组了，并没有把第一组全部排完。
int gap; for (int i = 0; i < n - gap; i++) { //子序列 int end = i; int tmp = a[end + gap]; while (end >= 0) { if (tmp < a[end]) { a[end + 3] = a[end]; end -= gap; } else { break; } } a[end + gap] = tmp; }
希尔排序代码
分析
gap越大，大的值更快调到后面，小的值更快调到前面，越不接近有序。
gap越小，大的值更慢调到后面，小的值更慢调到前面，越接近有序。
当gap为1，就是直接插入排序。
所以我们这里的gap值应该是在变化的，一般我们随n变化，取gap = gap/3+1，或者gap = gap/2;
void ShellSort(int* a,int n)
{
int gap = n;
while (gap>1)
{
gap = gap / 3 + 1;
for (int i = 0; i < n - gap; i++)
{
//子序列
int end = i;
int tmp = a[end + gap];
while (end >= 0)
{
if (tmp < a[end])
{
a[end + gap] = a[end];
end -= gap;
}
else
{
break;
}
}
a[end + gap] = tmp;
}
}
}这里无论gap是奇数还是偶数，这里gap最终都会除以到值为1。
gap>1时是预排序，目的让其接近有序。
gap=1时是直接插入排序，目的让其有序。
在gap=1时，已经十分接近有序了
代码测试
时间复杂度分析
希尔排序的时间复杂度并不固定，它依赖于所选择的间隔序列（增量序列）。直到今天，已经有多种不同的间隔序列被提出来，每种都有自己的性能特点。
《数据结构(C语言版)》--- 严蔚敏
《数据结构-用面相对象方法与C++描述》--- 殷人昆
因为咋们的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照：O(N^1.25) 到 O(1.6* N^1.25) 来算。
希尔排序的特性总结：
时间复杂度：O(N²)
空间复杂度：O(1)
稳定性：不稳定
复杂性：简单
如有错误，请指正
原文地址：https://blog.csdn.net/weixin_65132948/article/details/142423392
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！