排序的秘密（1）——排序简介以及插入排序

前言：

小编在n日之前曾经写过数据结构相关的内容，我依稀记着当初我写的是二叉树相关的内容，这几天由于我一直在学习C++的相关内容，导致我的排序一直没有复习，于是我痛定思痛，抽时间又学习了一遍排序算法，所以诞生了这一篇文章，下面我不多说废话，代码时间到~

1.排序概念以及应用

1.1.概念

排序：所谓排序，就是是一串记录，按照其中的某个或某些关键字的大小，递增或者递减的排序起来的操作。从这可以看出，希尔排序是在直接插入排序的基础上，对代码进行了改善，从而让其效率更高，时间复杂度更低，对于它的时间复杂度，我会在讲完代码后简单说说，下面我们进入希尔排序的理论部分讲解。这个词在我们生活中是很常见的，下面小编就展示一下在我们生活中排序的应用。

2.2.3.代码讲解

对于这部分的代码讲解，其实很简单，它和上面的直接插入排序其实是很像的，只不过上面的直接插入排序是一个一个的进行比较，所以此时的end是直接–操作的，而希尔排序是分组排序的，所以每次排序的时候都得end - gap，通过小编在前文的简介，就可以知道此时我们首先写的循环应该是关于gap的，让每次gap / 3 + 1，这里小编就解释一下为什么此时我们不仅要除以3还需要加1，加1是因为避免出现6这种情况，这样的话会让代码直接出错，毕竟6连续除以3以后，最后会得出gap是0，gap是0的话直接就不用排序了，并且如果此时我们在定循环的条件是gap > 0的话，就不会让gap为1，从而无法实现最后一步——直接插入排序，所以小编此时+1的目的是为了最后会出现gap为1的情况，所以此时我们就要写一个while循环，它循环的条件就是gap > 1，倘若gap == 1，则会陷入死循环，因为%一个数在+1，最后的结果肯定会往1靠近的，所以我们最外层的循环就是while循环，如下所示：

int n; //代表数组元素个数int gap = n;while(gap > 1){    gap = gap / 3 + 1;    //此时这里有个for循环，写法在下面}

下面我们还需要一个循环，这个逊汗便就是完成一个预排序，它的格式和直接插入排序是类似的，只不过不同点是循环结束的条件，之前是i < n - 1，而这里则因为分组，得出来的结论应该是i < n - gap，因为此时我们数组在n - gap - 1的位置，就要去到它下一个组员的数据，也就是n - 1，所以这便是结束条件，至于循环里面的内容，则是和直接插入循环差不多的，就和套用模版一样，这个循环我们顺理成章就可以写出来了：

for(int i = 0 ; i < n - gap ; i++){    int end = i; //通过i来进行小的排序    int tmp = arr[end + gap];}

​ 当然我们不仅仅要写这个循环，还有一个循环小编没有写出来，就是对组里的元素和tmp分别进行比较，如果end的数据大于tmp，那么就让end + gap位置的数据放置end，让end - gap，直到end < 0或者end位置的数据小于tmp，则就让循环结束，然后让end + gap的数据放置tmp，这便是最后一个循环书写：

while(end > 0){    if(arr[end] > tmp)    {        arr[end + gap] = arr[end];        end = end - gap;    }    else    {        break;    }}arr[end + gap] = tmp;

之后希尔排序的代码我们就完成了，下面小编放上完整的源码并和各位浅谈一下时间复杂度：

void ShellSort(int* arr, int n){	int gdp = n;	while (gdp > 1)	{		gdp = gdp / 3 + 1;  //为了避免n == 6这种情况，会陷入死循环		for (int i = 0; i < n - gdp; i++)		{			int end = i;			int tmp = arr[end + gdp];			while (end >= 0)			{				if (arr[end] > tmp)				{					arr[end + gdp] = arr[end];					end = end - gdp;				}				else				{					break;				}			}			arr[end + gdp] = tmp;		}	}}

2.2.4.浅谈时间复杂度

可能很多读者朋友看到上面的源码，会疑惑这三层循环为什么比两层循环的直接插入排序更好？不应该是更差吗，其实这样就错了，循环嵌套多了!=时间复杂度会很高，就以此时希尔排序的时间复杂度来说，其实它的时间复杂度是较于直接插入排序是好点的，希尔排序的复杂度不太好计算，因gap的取值可以有很多，导致很难去计算，因此很多书中的希尔排序的时间复杂度都是不固定的，小编学习到的时间复杂度大致是O(N ^ 1.3)，在《数据结构（C语言版）》，严蔚敏老师给出的时间复杂度是：

综上所示，希尔排序的时间复杂度是优于直接插入排序的，不然它也不会被称之为优化后的直接插入排序，当然，我们在代码实现的过程中，千万不要写成我之前说的那样分组排序后在分组排序，那样的时间复杂度是很高的。实际上我们在玩扑克牌的时候，就用到了插入排序的思想。

void InsertSort(int* arr, int n)  //这里我实现的是升序的数组，想要实现降序的话，各位大佬听完上面应该就知道怎么做了{	for (int i = 0; i < n - 1; i++)	{		int end = i;		int tmp = arr[end + 1];		while (end >= 0)		{			if (arr[end] > tmp)   //这里直接把>变成<即可。
以上便就是直接插入排序的理论部分，下面我们进入实践部分，那就是代码实操喽~
2.1.2.代码讲解
对于这部分的代码讲解，我认为有了前面的理论铺垫以后，便是很好去实现了，此时我们难免会遇到会碰到我们的老朋友，那就是for循环，此时这个for循环最主要的作用就是不断的更新end的位置，通过每一次小小的排序最后促成一个大的排序，此时我们确认end位置的数据就好了，以及保存好tmp的值，如下面代码所示：
int arr[10];  //这里的值取决于你想要排序数的个数int  sz = sizeof(arr) / sizeof(int);for(int i = 0 ; i < sz - 1; i++)   //因为此时的tmp总要比end多一个，所以为了保证tmp不会访问到越界数组的数，这里我直接{    int end = i;  //记录每一次i的位置    int tmp = arr[end + 1];}
之后我们就要来到这个排序的精华部分了，也就是我们还需要用到循环，此时循环的条件就是end的底线，假如end<0了，那么自然而然的我们就知道额了此时已经来到了数组第一个元素的位置，所以我们直接把tmp放到end + 1就好了，之后谈一谈循环体内部，来判断end以及其之前的位置的数据进行和tmp的比较，如果end位置的数据大于tmp，则把end位置的数据放置到end + 1的位置，之后我们再让end–，假如此时end位置的数据本身就比tmp小了，那么我们就可以结束循环立刻，因为理论我说过，end前面的位置本身就比end小了，自然和tmp就没有可比性了，然后我们再把tmp放到end + 1就好了：
//这里承接上面的循环体内部，我就不水代码了while(end > 0){    if(arr[end] > tmp)    {        arr[end + 1] = arr[end];        end--;    }    else    {        break;    }}arr[end + 1] = tmp;
此时我们就完成了直接插入排序的代码，下面小编直接把完整的直接插入函数代码展示出来，然后我们浅浅的分析一下和这个算法的时间复杂度。
之后我们再让end的位置到5这个元素的位置，tmp仍然是end + 1的数据也就是9，此时我们继续比较end和tmp的大小，此时的end小于tmp，此时我们也不用比较end之前的数据和tmp数据的大小了，因为经过简单排序以后，此时的end左边的数据肯定都比end小的，所以此时我们无须排序，直接让end到下一个位置继续比较：
此时end位置的数据肯定要比tmp大，那么我们让end + 1位置数据变成end的数据，然后我们让end–，此时end要小于tmp的值，所以这里的end不需要动了，只需要end + 1的数据为tmp就好了，然后我们继续重复这样的操作，这样我们就可以完成一个数组的排序了。
首先，我们还是要准备好一个数组，这里允许我偷个懒，还是拿上面的数组进行排序：
这里我们还是要有两个指针，也就是end和tmp，还要多一个gap作为分组依据，通过数数，我们知道上面的数组有9个数据，所以正好可以分为3组进行计算，这里我先分个组：
咳咳，虽然上面比较混乱，但这确实就是一个数组的划分，之后我们其实和上面的直接插入排序差不多，只不过此时，tmp不再是end + 1的数据了，而是end + gap的数据，分组分组，我们比大小也要和自己组里的数据进行比大小，所以此时end 是和 end + gdp进行比大小，比完一次大小以后，倘若end大于tmp的数据，我们不再是end + 1 = end，而是让end + tmp = edn，让组里下一个位置的数据接受end的值，之后如果end小于0或者end < tmp的数据，那么我们就结束循环，然后让end + tmp的数据变为tmp，这样我们就完成了一次循环，此时上图end的位置是第一个位置的数据，此时end < tmp，所以直接不用动数据，然后让end变为第二个位置，可能这里有很多读者朋友会奇怪，我为什么不一个组一个组进行比较，而还是让每一个元素在自己组内比较，这其实是有原因的，因为如果这么做的话，等会代码实现部分，我们会写成三个大循环嵌套，直接让其时间复杂度变得更加的复杂，这并不会起到优化代码的作用，反而起到了劣质化代码的作用，所以这种方法是万万不可以的，本来小编要在后面的代码说的，既然我从这里说了，那么我就直接简单说说了。
首先，我们需要先需要一个数组作为排序的目标，这里小编就拿下面的数组展示了：
数组问题解决好以后，下面我们就要设置好两个“指针”了，其中一个叫做end，负责遍历每一个元素的，还有一个tmp，记录end笑一个位置的值，此时我们就可以开始进行排序了，首先我们比较end和tmp的大小，很明显，end此时的值大于tmp，所以我们把end的数据给end + 1，之后end–，此时的end < 0，那么就直接让end + 1的数据为tmp就好了，此时我们就完成了第一次范围排序。