【初阶数据结构】详解插入排序 && 希尔排序（内含排序的概念和意义）

前言

初级数据结构系列已经进入到了排序的部分了。相信大家听到"排序"这个词，第一时间会想到冒泡排序，因为这个是大家学习C语言时，遇到的第一个真正意义上的排序算法。那么在这个系列中，有八大排序算法，都会给大家一一讲解它的实现思路，以及对应的代码实现！

那么在本文中，我们就开启排序算法的第一个章节 —— “插入排序” 和 “希尔排序”。

1. 排序的概念及其应用

在正式讲解插入排序和希尔排序之前，我要带着大家理解我们为什么需要排序？以及排序在我们生活中有什么应用？学完这些之后，大家也许对排序算法就不会那么迷茫了。

1.1 排序的概念

排序：所谓排序，就是时一串记录，按照我们特定且可行的想法，递增或递减的排列起来的操作。

排序是一项操作！

1.2 排序的应用

看到这里，大家可以打开京东商城，当你想买一台新的手机时，却不知如何入手。你可能会选择按好评数来进行排序，从而选出好评率最高的手机。在这个过程，就用到了排序的思想。

再如，我们的大学按照教学资源以及教学能力，也能进行排序：

当然，生活中还有很多例子都是用到了排序的思想。这就是所谓处处有排序！

好了，在了解完排序的重要性之后，我们就要正式迈入学习插入排序和希儿排序的殿堂中了。

2. 插入排序

插入排序，通常我们也称它为直接插入排序。

2.1 基本思想

在一个有序的数组中，按照一定的规则插入待排序的数字。

详细一点说的话，就是：

算法思路：
先从单趟排序讲起，我们可以选择待插入的数字与从排序好的数组末端的数进行比较。若发现该值比待插入的数字要大，则将盖子往后挪动一位，接着继续往前面进行比较。若发现该值比待插入的数字要小，说明该值的后面一个位置就是待插入数字应该插入的位置，我们就可以结束循环了。

单趟排序讲完了之后，就可以将一个完整的插入排序了。
如果你真的认证解读了单趟插入排序的思路，你会发现插入排序不过如此！

其实一个完成的插入排序就是在循环地跑单趟排序，循环地初始条件为从待插入数组的第二个元素小标开始。每当单趟排序跑完之后，我们都得设置循环条件的值(一开始比较数组末端的位置)。因为你已经排好了部分数组，每当来一个新数字就得在拍好数组中插入，重复上述过程。

下面我给大家展示插入排序算法的动图，希望大家能够结合上述的话语，仔细观看：

2.2 插入排序的代码实现

void InsertSort(int* a, int n)
{
	for (int i = 1; i < n; i++)
	{
		int end = i - 1; //待排序数组的末端
		//也可以写成int tmp = a[end + 1]; 
		int tmp = a[i];  //tmp存放的是待插入的数值
		while (end >= 0)
		{
			if (tmp < a[end]) //待插入数字与数组末端的值进行比较
			{
				a[end + 1] = a[end];
				end--;
			}
			else
			{
				break;
			}
		}

		a[end + 1] = tmp;
	}
	
}

2.3 插入排序算法总结

根据上面的代码，我们可以总结出一些关于插入排序算法的特征：

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

3. 希尔排序

希尔排序又称缩小增量排序。

3.1 基本思想

先选定一个整数(gap)，把待排序的数据分成个别组。分组的标准就是所有距离为gap的数据分在同一组，并对每一组内的记录进行排序。然后，缩小gap的值，重复上述分组和排序的工作。当gap = 1时，就相当于直接插入排序了。

上面这个思想很重要，是理解希尔排序的核心！

给大家举个例子：

3.2 希尔排序的代码实现

void ShellSort(int* a, int n)
{
	int gap = n;
	while (gap > 1)
	{
		//gap /= 2;
		gap = gap / 3 + 1;
		for (int j = 0; j < gap; j++)
		{
			//就是在对每组(隔gap位置的数字)的数据进行插入排序
			for (int i = j; i < n; i += gap)
			{
				int end = i - 1;
				int tmp = a[i];
				while (end >= 0)
				{
					if (tmp < a[end])
					{
						a[end + 1] = a[end];
						end--;
					}
					else
					{
						break;
					}
				}

				a[end + 1] = tmp;
			}
		}
	}

3.3 希尔排序的特征总结

• 希尔排序是对直接插入排序的优化。
• 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。我们实现后可以进行性能测试的对比。
• 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算。但是我们一般认为希尔排序算法的时间复杂度为O($N\ast logN$)，但是如果我们是追求一个严谨读者，那它的时间复杂度为O(N^1.3)。

好了，到这里本文就结束了。如果觉得本文还不错的话，麻烦给偶点个赞吧！