数据结构排序算法之直接插入排序与希尔排序【图文详解】

P. S.：以下代码均在VS2019环境下测试，不代表所有编译器均可通过。 P. S.：测试代码均未展示头文件stdio.h的声明，使用时请自行添加。

在这里插入图片描述

                        博主主页：LiUEEEEE
                        C语言专栏
                        数据结构专栏
                       力扣牛客经典题目专栏

1、排序的概念

排序：所谓排序，就是使一串记录，按照其中的某个或某些关键字的大小，递增或递减的排列起来的操作。
稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。
内部排序：数据元素全部放在内存中的排序。
外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不断地在内外存之间移动数据的排序。

2、直接插入排序

直接插入排序是一种简单的插入排序法，其基本思想是：

把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

实际中我们玩扑克牌时，就使用了插入排序的思想
在这里插入图片描述

直接插入排序的动态图如下所示：

图中所示可以理解为：

将数组的前 n 项视作有序（此时的 0 < n

其代码如下所示：

void Insert(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)令数组从下标为1的位置一直循环判断到下标为n的位置，对应的为循环内的tmp所在位置
	{
		int end = i;
		int tmp = a[end + 1];暂存的数值，其下标为end + 1
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
				break;
		}
		a[end + 1] = tmp;即使判断到数组下标为0的位置，也不会发生越界，此时的end为-1，a[end + 1]所对应的正好为数组下标为 0 的位置。
	}
}

直接插入排序的特性总结：

元素集合越接近有序，直接插入排序算法的时间效率越高
时间复杂度：O(N^2)
空间复杂度：O(1)，它是一种稳定的排序算法
稳定性：稳定

3、希尔排序（缩小增量排序）

希尔排序实在直接插入排序基础上进行优化的排序算法，其基本思想为：

先选定一个整数，把待排序文件中所有记录分成个组，所有距离为的记录分在同一组内，并对每一组内的记录进行排序。然后，取，重复上述分组和排序的工作。当到达=1时，所有记录在统一组内排好序。

上文的基本思想原理如下图所示，例如有示例数组，其成员为5，3，7，9，2，1，4，6，8：

在这里插入图片描述
我们令gap = 3，将下标间隔为gap的数组成员分成新的一组，下图中相同连线颜色代表同组：

在这里插入图片描述
将逻辑上的三个新数组分别使用直接插入法进行排序（本文中所演示的均为升序），结果如下所示：

而后将三个新数组按其在原数组的位置在逻辑上合并，结果如下所示：

在这里插入图片描述
事实上，经过gap = 3 的分组插入排序后，新的数组较原有数组更为有序，此时的示例可能还不足以让看官们一眼看出其中的差别，故将gap - 1，及gap = 2，继续进行分组插入排序，其示意图如下，并附带结果展示：

在这里插入图片描述
经过gap = 2 的分组插入排序后，可以发现新的数组具有比原数组更高的有序度，此时按照希尔排序的基本思想，继续将gap - 1，再进行最后一次的插入排序，其结果如下所示：

此时我们的原数组就完全的有序化了（升序）。

希尔排序的特性总结：

希尔排序是对直接插入排序的优化。
当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就
会很快。这样整体而言，可以达到优化的效果。
希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些树中给出的
希尔排序的时间复杂度都不固定：

因为咋们的gap是按照Knuth提出的方式取值的，而且Knuth进行了大量的试验统计，我们暂时就按照上图所示蓝色框选范围来算算。
稳定性：不稳定

4、为何拥有了插入排序还出现了希尔排序

其原因是因为当所需排序内容数据量偏大时，直接插入排序需对每一个成员进行判别，拥有时间复杂度上的浪费，而希尔排序的出现，引入了一个预排序的概念，将原数据量分为n组，对每组成员内的数据进行有序化，每一次的进行都会让原有数据更加有序，所以当gap = 1时，及对原有数据进行完全的直接插入排序，就不需再比较多组数据，既避免了时间的浪费，又提高了排序的效率，本段中所指 gap 在研究者的研究下暂定以gap = 3开始效率较高，故后续使用中也可以gap = 3 来进行希尔排序的预排序。

5、完整代码及效果展示：

test.c

#include 

void Swap(int* p1, int* p2)
{
	int tmp = *p1;
	*p1 = *p2;
	*p2 = tmp;
}

void Insert(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)
		{
			if (tmp < a[end])
			{
				a[end + 1] = a[end];
				end--;
			}
			else
				break;
		}
		a[end + 1] = tmp;
	}
}

void ShellSort(int* a, int n)
{
	for (int i = 3; i >= 1; i--)
	{
		int gap = i;
		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;
		}
	}
}

void test()
{
	int a1[] = { 13,56,35,76,45,74,37,82,546,245,736,165,826,825 };
	int size1 = sizeof(a1) / sizeof(a1[0]);
	int a2[] = { 13,56,35,76,45,74,37,82,546,245,736,165,826,825 };
	int size2 = sizeof(a2) / sizeof(a2[0]);
	Insert(a1, size1);
	for (int i = 0; i < size1; i++)
	{
		printf("%d ", a1[i]);
	}
	printf("\n");

	ShellSort(a2, size2);
	for (int i = 0; i < size2; i++)
	{
		printf("%d ", a2[i]);
	}
	printf("\n");

}

int main()
{
	test();

	return 0;
}

上述代码块中直接插入排序与希尔排序所排数组为成员相同的不同数组，其排序结果如下所示：
在这里插入图片描述

6、结语