从零开始学数据结构系列之第六章《希尔排序》

---

希尔排序

插入排序的问题

逆序有序的数组排序时，时间复杂度为O ( n 2 ) O(n^2)O(n 2)，此时效率最低

顺序有序的数组排序时，时间复杂度为O ( n ) O(n)O(n)，此时效率最高

​ 我们发现，当被排序的对象越接近有序时，插入排序的效率越高，那我们是否有办法将数组变成接近有序后再用插入排序，此时希尔大佬就发现了这个排序算法，并命名为希尔排序

希尔排序的原理

希尔排序是对直接插入排序的优化

​ 希尔排序是一种改进的插入排序算法，也被称为缩小增量排序。它通过比较相距一定间隔的元素来排序，然后逐渐缩小这个间隔，直到最后一次比较相邻元素进行排序，从而实现整体的排序。

• 希尔排序改进了直接插入排序，先让数组大致有序，最后直接插入排序，此时直接插入性能插入最好
• 希尔排序比较适合大批量的杂乱无章的数据
• 希尔排序的算法效率肯定是比直接插入排序的效率要高的，要排序的数据量越大，希尔排序的优势就越明显

希尔排序的步骤

大致步骤

​ 希尔排序是对插入排序的优化，基本思路是先选定一个整数作为增量，把待排序文件中的所有数据分组，以每个距离的等差数列为一组，对每一组进行排序，然后将增量缩小，继续分组排序，重复上述动作，直到增量缩小为1时，排序完正好有序。

希尔排序原理是每一对分组进行排序后，整个数据就会更接近有序，当增量缩小为1时，就是插入排序，但是现在的数组非常接近有序，移动的数据很少，所以效率非常高，所以希尔排序又叫缩小增量排序。

​ 每次排序让数组接近有序的过程叫做预排序，最后一次插入是直接插入排序

分租思想

我们分组一般是以步长作为分组的依据

那什么叫做步长呢？

可以简单的理解为相隔的个数，也可以理解为向前走五步这样子的

上图中gap为5，说明要分成5组。
这5组分别用了五种颜色的线条连接起来了。

• 第1组：9、4
• 第2组：1、8
• 第3组：2、6
• 第4组：5、3
• 第5组：7、5

为什么要采取上面的分组方法呢？换一种方法可以吗？
例如：挨着的元素分为一组。

如果是上面的这种分组方式的话，排序之后会变成下面的情况。

如果是最开始的分组方法的话

如果是按照最开始的分组思想分组的话，最后会排序成

可以发现如果先以步长小的都是叫小的数据，比较难方便分组。

排序例子

待排序图：

首先我们先确定步长，那我们先假设步长为5

开始分组，那么：

我们根据颜色不同进行分组

那么：我们先分组，然后将组内顺序进行一个排序

分组			排序
49	13		13	49
38	27		27	38
65	49		49	65
97	55		55	97
76	4		4	76

那最后能得到这个结果：

后面我们在一步长缩小一倍来看，也就是步长为2(也可以为3)的情况

那我们进行一个分组

分组						排序
13	49	4	38	97		4	13	38	49	97
27	55	49	65	78		27	49	55	65	78

后面我们在一步长缩小一倍来看，也就是步长为1的情况，也就是我们的插入排序

总代码

#include <stdio.h>void printArray(int array[], int length) 
{int i;for (i = 0; i < length; i++) {printf("%d ", array[i]);}printf("\n");
}void shellSort(int array[], int length, int step) 
{int i,j,k,temp,l;for (i = 0; i < length; i++) {for (j = i + step; j < length; j += step) {for (k = i; k < j; k += step) {if (array[j] < array[k]) {temp = array[j];for (l = j - step; l >= k; l -= step) {array[l + step] = array[l];}array[k] = temp;}}}}
}int main()
{int i;int array[10] = {49, 38, 65, 97, 76, 13, 27, 49, 55, 4};int steps[3] = {5, 3, 1};for (i = 0; i < 3; i++) {shellSort(array, 10, steps[i]);printArray(array, 10);}return 0;
}

---

☁️ 以上就是所有内容，对大家有用的话点个关注！感谢大家！

往期回顾

1.【第一章】《线性表与顺序表》
2.【第一章】《单链表》
3.【第一章】《单链表的介绍》
4.【第一章】《单链表的基本操作》
5.【第一章】《单链表循环》
6.【第一章】《双链表》
7.【第一章】《双链表循环》
8.【第二章】《栈》
9.【第二章】《队》
10.【第二章】《字符串暴力匹配》
11.【第二章】《字符串kmp匹配》
12.【第三章】《树的基础概念》
13.【第三章】《二叉树的存储结构》
14.【第三章】《二叉树链式结构及实现1》
15.【第三章】《二叉树链式结构及实现2》
16.【第三章】《二叉树链式结构及实现3》
17.【第三章】《二叉树链式结构及实现4》
18.【第三章】《二叉树链式结构及实现5》
19.【第三章】《中序线索二叉树理论部分》
20.【第三章】《中序线索二叉树代码初始化及创树》
21.【第三章】《中序线索二叉树线索化及总代码》
22【第三章】《先序线索二叉树理论及线索化》
23【第三章】《先序线索二叉树查找及总代码》
24【第三章】《后续线索二叉树线索化理论》
25【第三章】《后续线索二叉树总代码部分》
26【第三章】《二叉排序树基础了解》
27【第三章】《二叉排序树代码部分》
28【第三章】《二叉排序树代码部分》
29【第三章】《平衡二叉树基础概念》
30【第三章】《平衡二叉树的平衡因子》
31【第三章】《平衡二叉树的旋转基础详解》
32【第三章】《平衡二叉树的旋转类型图文详解》
33【第三章】《平衡二叉树的旋转类型总结及总代码》
34【第三章】《哈夫曼树简单了解》
35【第三章】《哈夫曼树的构造方法》
36【第三章】《哈夫曼编码构造及代码》
37【第四章】《图的定义》
38【第四章】《图的基本概念和术语》
39【第四章】《图的存储结构》
40【第四章】《图的遍历之深度优先遍历》
41【第四章】《广度优先遍历BFS》
42【第四章】《图的遍历总代码》
43【第四章】《最小生成树概念》
44【第四章】《最小生成树的应用举例》
45【第四章】《prim算法（普里姆算法）详解》
46【第四章】《prim算法（普里姆算法）详解2》
47【第四章】《prim算法（普里姆算法）详解3》
48【第四章】《prim算法（普里姆算法）讲解汇总》
49【第四章】《prim算法（普里姆算法）代码讲解》
50【第四章】《prim算法（普里姆算法）总代码》
51【第四章】《克鲁斯卡尔算法思路介绍》
52【第四章】《克鲁斯卡尔算法步骤思路1》
53【第四章】《克鲁斯卡尔算法步骤思路2》
54【第四章】《克鲁斯卡尔算法应用场景-公交站问题》
55【第四章】《克鲁斯卡尔算法判断回路问题》
56【第四章】《克鲁斯卡尔算法步骤回顾》
57【第四章】《克鲁斯卡尔算法代码初始化详解》
58【第四章】《克鲁斯卡尔算法总代码详解》
59【第四章】《了解最短路径》
60【第四章】《迪杰斯特拉算法了解》
61【第四章】《Dijkstra 迪杰斯特拉算法图解》
62【第四章】《Dijkstra 迪杰斯特拉算法总代码》
63【第四章】《弗洛伊德(floyd)算法简介》
64【第四章】《弗洛伊德算法详解》
65【第四章】《弗洛伊德代码详解》
66【第四章】《拓扑排序之AOV网》
67【第四章】《拓扑排序介绍及其方法》
68【第四章】《拓扑排序代码详解》
69【第四章】《什么是关键路径》
70【第四章】《什么是关键路径二》
71【第四章】《关键活动与最早路径实现思想》
72【第四章】《关键活动与最早路径实现思想写法二》
73【第四章】《关键路径总代码讲解写法一》
74【第四章】《关键路径总代码讲解写法二》
75【第五章】《顺序查找》
76【第五章】《顺序查找-带哨兵》
77【第五章】《二分查找》
78【第五章】《B树了解以及定义》
79【第五章】《B树的插入例子1》
80【第五章】《B树的插入例子2》
81【第五章】《B树的删除》
82【第五章】《B树的删除2》
83【第五章】《B树的代码部分》
84【第五章】《B树的总体代码》
85【第六章】《排序简介》
86【第六章】《插入排序》