希尔排序（C语言实现）

目录

1.希尔排序( 缩小增量排序 )

2.动图 ​编辑

3.代码实现

预排序实现 

子序列排列实现

单趟排序实现

对整组数进行子排序

希尔排序代码

代码测试 

 时间复杂度分析

希尔排序的特性总结：

---

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)

稳定性：不稳定

复杂性：简单

---

---

如有错误，请指正