【数据结构】-插入排序家族（直接插入排序、希尔排序）_数据结构插入排序

作者：小树苗渴望变成参天大树
作者宣言：认真写好每一篇博客
作者gitee:gitee

如 果 你 喜 欢 作 者 的 文 章 ，就 给 作 者 点 点 关 注 吧！

前言

今天我们介绍关于插入排序，插入排序分为两种，一个是直接插入排序，一个是希尔排序，这两种排序是由相同之处的，那我们接下来介绍一下这两种排序。(以升序进行讲解)

一、直接插入排序

我们先来看看动图演示：

我们是一步一步往后面走，遇到大的就往后面移一位，知道碰到一个小的，就把数据往小的后面进行插入。我们先来看看单趟排序：

	int end = 9;
		int key = a[end];//先把要插入的数据保存起来，方便和其他数进行比较
		while (end >= 0)
		{
			if (key < a[end - 1])//可以小于前面的数，就把数往后面移一位
			{
				a[end] = a[end - 1];//
				  end--;
			}
			else//比前面a[end-1]的这位大就退出，把数据放到它后面，就是a[end]的位置
			{
				break;
			}
		}
		a[end] = key;//把要插入的数放到这个位置
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

单趟排序结果：

我们看画图：

在实际排序中，开始排最后一位数的时候，前面应该是有序的了，我们都市从前面往后面选出key进行插入，但是每一趟的思想是样的。

我们来看看完整的排序：

void insertsort(int* a, int n)
{
	for (int i = 1; i <= n-1; i++)//i从1开始就可以了，没必要从0开始
	{
		int end = i;
		int key = a[end];//先把要插入的数据保存起来，方便和其他数进行比较
		while (end > 0)//因为都是和前面的数进行，加等于就跳到前面的位置，越界了，
		{
			if (key < a[end - 1])//可以小于前面的数，就把数往后面移一位
			{
				a[end] = a[end - 1];//把前面大的数移到后一位
			   end--;
			}
			else//比前面a[end-1]的这位大就退出，把数据放到它后面，就是a[end]的位置
			{
				break;
			}
		}
		a[end] = key;//把要插入的数放到这个位置
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

大家掌握这个思想之后我们开始进行希尔排序的讲解

二、希尔排序

希尔排序是在直接插入排序的基础上先进行分组，然后预排序，增加分组，在排序，最后就排序成功，我们来看看图：

对分组的元素进行直接插入排序，我一开始先以三个为一组距离为二的gap给大家画图演示一下，更加的直观一些

这就是希尔的一趟排序，但实际代码是一个一个的往后面走的，我知识把距离为gap的分开画图让大家看到更加直观些，我们来看看这一趟排序的代码，再来看看整体的：

int gap = 2;
	for (int i = gap; i <=n - gap; i++)
	{
		int end = i;
		int key = a[end];
		while (end > 0)
		{
			if (key < a[end - gap])
			{
				a[end] = a[end - gap];
				end -= gap;
			}
			else
			{
				break;
			}
		}
		a[end] = key;
	}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

我们针对直接插入排序仅仅就做了很小的变化，把gap变成1就是直接插入排序。

单趟排序的结果：

我们只要保证最后一次gap=1就行了，所以我们还有一种写法
gap=gap/3+1；
这是我们给gap初始值的方法

void shellsort(int* a, int n)
{
	int gap=n;
	while (gap > 0)
	{
	   gap = gap/2;
	   gap=gap/3+1;
		for (int i = gap; i <= n - gap; i++)
		{
			int end = i;
			int key = a[end];
			while (end > 0)//因为都是和前面的数进行，加等于就跳到前面的位置，越界了，
			{
				if (key < a[end - gap])
				{
					a[end] = a[end - gap];
					end -= gap;
				}
				else
				{
					break;
				}
			}
			a[end] = key;
		}
		gap/=2;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28

对于希尔排序，为什么效率比直接插入排序好，原因是gap>1的时候，都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。

希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的希尔排序的时间复杂度都不固定

我们来看看其他书中是怎么介绍希尔排序的时间复杂度：
《数据结构(C语言版)》— 严蔚敏

《数据结构-用面相对象方法与C++描述》— 殷人昆

这个我们能记住结论更好，不能记住了解一下也可以，我们先要掌握每一趟的排序，在对整体进行排序，这样即使忘记了，画画图也很快就能掌握了。

三、总结

今天我讲的两种排序都是插入排序家族的，两种有相似之处，也有不同之处，两者的性能差距，我会再更新所有排序的文章之后再进行测试，那今天的排序就先将到这里了，大家下来自己去画画图理解一下，我们下篇讲选择排序家族的