本文我们来讲一下常见十种经典排序算法中的插入排序与希尔排序

@TOC

🌳排序的概念意义及总括

所谓排序，就是使一串记录，按照其中得某个或某些关键字得大小，递增或递减地排列起来的操作

📚内外排序的复杂度及稳定性

• 所谓复杂度有时间复杂度和空间复杂度，每种排序算法都有它们各自的复杂度

• 什么叫做稳定性呢，所谓稳定性，就是当多个相同的关键字记录，经过排序后，这些记录得相对次序保持布标，则成为该算法是稳定的

• 下面是一些内外排序的复杂度及稳定性:point_down:

📚排序的应用

• 对于排序，我们在生活中的许多场景中都有见到过，比如说买东西时的物品价格排序；又比如在高考填报志愿时一些全国大学的排名

🌳插入排序

了解了排序的基本理念后，接下来我们来进入第一个排序算法，也就是——插入排序

• 对于插入排序，你可以理解成我们在打扑克时对手中拥有的扑克进行的一个排序，因为可能会将后面得一张牌抽出来将其放到前面那些已经排好序的牌堆中，这时就要比较大小了

🐚如何将一个数放入有序序列中？

• 那将一个数字插入一个有序序列中具体是一个怎样的写法呢❓

• 从上面这张图我们可以看出，首先要先取到前面有序序列的最后一个位置，然后在这个位置的后面取一个数字，去前面作比较，若是比前面一个数小，则将前面数字进行一个依次后移
• 然后一定会空出一个位置，这个时候就将待插数字放入这个位置即可
• 接着在外部我们需要控制的是取数字的操作，也及时在做牌时放完一张扑克牌要接着放下一张扑克，我们用for循环来控制

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;

	PrintArray(a, n);
}

• 但是有一点要注意的是这个==for循环结束的位置==，不可以是n，而是n - 1，因为我们后面要去取这有序序列得最后一个位置得后一个位置，若是到n才结束，那么这时end + 1就会越界，导致程序出现错误
• 观看代码，将这个end + 1位置的数字与前面的数进行比较，若是比前面的小，则执行后移换位操作，然后这个end的值要前移，若是tmp的值要来的大或是相等，这时我们应该进行一个换位操作，但是这里的else分支为什么写的是break呢，我们来看一种特殊情况:gift:

• 当前的这个tmp的值为1，可以知道，它是要移动到最前面去的，但是当此时end移动到最左边位置时，再次进入while循环，此时若是执行a[end + 1] = a[end];就不对了，此时end所指向的位置是数组的外界，因此这时我们应该进入else分支
• 面对这两种情况，最后的赋值其实都是a[end + 1] = tmp，所以我们应该将此语句放到while循环的最后，在执行到else语句时使用break跳出循环即可

🐚结果测试

• 我们来看一下最终的显示结果，这里是==逐循环的追踪打印==，可以很清晰地看出每次元素的变化情况

• 这是封装好的PrintArray函数和主函数

void PrintArray(int* a, int n)
{
	for (int i = 0; i < n; ++i)
	{
		printf("%d ",a[i]);
	}
	printf("\n");
}

int main(void)
{
	int a[10] = { 9,3,8,0,2,4,1,7,5,6 };

	int sz = sizeof(a) / sizeof(int);
	puts("排序前的数组");
	PrintArray(a, sz);


	puts("排序后的数组");
	InsertSort2(a, sz);

	//PrintArray(a, sz);
	return 0;
}

🐚时间复杂度分析

了解了排序的基本算法实现后，我们来看一看插入排序的时间复杂度是多少:balloon:

• 对于时间复杂度的话，我们应该要首先考虑到最坏的一种情况，也就是下面的第一种，为什么说它是最坏的呢？
• 假设我们end 从下标0开始即10开始，9为end + 1，那么9要前移一位，然后下一个8又要前移两位，7要前移3位。。。以此类推，最后一个1要前移9位，这就是两个循环都需要去执行，那有n个数字，每个数字移动n次，时间复杂度就是==O(n^2^)==
• 但是看到第二种，已经是处于升序序列了，若end 从下标0开始即1开始，2为end + 1，那它根本不需要要移动，后的3、4、5也是一样，所以根本用不到内层得移位循环，只需要遍历一下这个数组就好了，假设传入的数字为n个，那么就是==O(n)==，这就是直插排序的最好情况

---

• 对于折半插入排序请看我的这一篇文章算法 | 二分法与折半插入排序【这是开端吗？】，我将此排序与二分查找结合起来说明

🌳希尔排序【缩小增量排序】

接下来我们来说说==希尔排序==，它隶属于插入排序，也就是插入排序延伸出来得

🍃基本思想和原理

• 基本思想：希尔排序又称缩小增量排序。是按照每次的gap值，也就是增量，对原本的数据进行一个分组，对每组使用直接插入排序算法排序。增量随着排序次数的增加而减少
• 当增量减少到1时，整个序列恰好被分为一组，算法便终止。

---

• 对于希尔排序，上面说过，其隶属于插入排序，是对直接插入排序的优化。
• 对于gap增量，当gap > 1时，都是对原先的数组进行的一个预排序，也就是将其接近有序；而当gap最终等于1时，则是已经接近有序，这时再用一次直接插入排序即可

光这样说明太过抽象，我们到画图工具里来演示一下:movie_camera:

🍃排序过程详解

• 首先说明，这个gap增量每次是以2的倍数递减

• 我们看到这里有10个数，因此gap = 10 / 2 = 5，也就是每个数字之间间隔为5，然后以将它们分为很多组，若是后者比前者大，则进行一个交换

• 上面是第二次排序后地结果，此时得gap = 5 / 2 = 2，所以增量为2的是一组

• 以上，便是第三次排序后的结果，可以看到，第三次得gap = 2 / 2 = 1，因为间隔为1，也就是全体数据为一组，那就是最后进行一次直接插入排序即可

🍃动画展示

我们通过动画再来回顾一遍

🍃代码分析

了解了希尔排序地内部排序过程，接下来我们来看看代码如何书写，为什么说它是插入排序的优化呢，你看了就知道了👀

void Shell_Sort2(int* arr, int n)
{
	int gap = n;
	while (gap > 1)
	{
		gap /= 2;		//log2N
		/*
		 * gap > 1时都是预排序 —— 接近有序
		 * gaop = 1 时为直接插入排序 —— 有序
		*/

		//gap很大时，下面预排序时间复杂度O(N)
		//gap很小时，数组已经接近有序，这时差不多也是(N)
		//把间隔为gap的多组数据同时排
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			int tmp = arr[end + gap];
			while (end >= 0)
			{
				if (tmp < arr[end]) {
					arr[end + gap] = arr[end];
					end -= gap;
				}
				else {
					break;
				}
			}
			arr[end + gap] = tmp;
		}
		Print_Array(arr, n);
	}

}

• 首先我们来看中间的一段代码，这其实就是直接插入排序的改良版，只是将【end + 1】改换成了【end + gap】而已，但这里可要注意，虽然只是改换了这么一小个地方，变化的程度可是相当地大
• 你将具体的值带入一演算一遍就可以知道，我们以gap = 5为例

• 首先看到end所指向得是这组数据得首元素，然后tmp所保存的是end + gap后的位置，因为tmp < arr[end]，因此9会移动到3的位置，此时end会向前移动gap个位置，这样数组就向前越界了，是的end < 0，然后便执行arr[end + gap] = tmp;这句话，这时才将9的位置放入3

• 接下来一步很重要，从上一步可以得知，此时的end又回到了最初的位置，然后又进入for循环i++，这个end就移到了5的位置，而tmp记录的则是2的位置

• 同理可得，推出下面这个样子，此时的end又回到了原来得位置

• 接下来end继续经过i++向后移，end此时指向7，tmp指向8，可以知晓，这不会进入第一个if分支，而会进入第二个else分支，此时break，强制跳出while循环，也可以进行一个换位

• 所以我们可以得出一个结论，这一次的排序并不是同一个中得多个数一起排序，而是不同组得多个数一个排序，增强了效率

int main(void)
{
	int arr[] = { 1,9,8,5,3,4,2,11,7 };
	int sz = sizeof(arr) / sizeof(arr[0]);

	std::cout << "数组排序前为：" << std::endl;
	Print_Array(arr, sz);

	Shell_Sort2(arr, sz);
	//std::cout << "数组排序后：" << std::endl;

	return 0;
}

• 以上就是我进行测试得一组数据，可以看出比直接插入排序得步骤要少了很多

🌳两种排序算法的时间复杂度深度分析

对于直接插入排序的时间复杂度，我们已经分析过了，我们来看看希尔排序的时间复杂度是怎样的

• 由代码中得gap这个增量我们可以知晓，它是一直处于一个折半缩小的过程，也就是每一次得到gap值都比上一次小一半，所以可以写出这样的表达式1 = N/2/2/2/2…，那么这个表达式又可以写成2^x^ = N即x = log~2~N
• 那根据【大O渐进法】我们可以知道这是一个O(logn)的时间复杂度
• 然后我们再来分析若是这个gap比较大的时候，每组数据得各个数字之间差距是很远的，它每次就来回得换一下或者不交换，这个时间复杂度趋近于O(n)
• 而当这个gap很小的时候，这个我们在上面有说到过，也就是gap == 1时，相当于只进行了一次内部得直接插入排序，那这个时间复杂度也是O(n)
• 因此外部控制gap的循环跑O(log~2~N)次，内部的交换跑O(n)，那么结合起来就是==O(Nlog~2~N)==
• 我们通过下面的时间复杂度趋势表示图可以看出

---

• 光是这样得理论数据分析太抽象了，接下去我们通过具体的数据来看看这个希尔排序到底比直接插入排序快多少❓
• 我们上面介绍的数据是10个，接下我们直接上10W个，这才能看出谁得算法性能更加优质一些

直接插入排序

• 那若这个N是10W的话，用直接插入排序O(n^2^)就是10W*10W也就是100亿，可见这个数据是非常得大

希尔排序

• 我们用希尔排序来试一下，N为10W的话O(Nlog~2~N)也就是100000*log~2~100000
• log~2~100000大家可能不会算，我们来算一下，我们知道2^10^ = 1024，2^20^ = 1024*1024，这也就是100W，那50W的话大概就是2^19^，25W的话大概就是2^18^，12.5W的话大概就是2^17^，那这个12.5W是不是和我们要求解得10W很相近呢，所以数据大概就是==100000 * 17 = 170W==
• 那其实就很清晰了，一个才170W，但是另一个却需要100亿
• 面对上面的这串数字，你希望哪个是你的年薪呢【doge】
• 就这么分析大家可能也看不出来，我们通过下面这串代码来跑一下

void TestOP()
{
 srand(time(0));
 const int N = 100000;
 int* a1 = (int*)malloc(sizeof(int)*N);
 int* a2 = (int*)malloc(sizeof(int)*N);
 int* a3 = (int*)malloc(sizeof(int)*N);
 int* a4 = (int*)malloc(sizeof(int)*N);
 int* a5 = (int*)malloc(sizeof(int)*N);
 int* a6 = (int*)malloc(sizeof(int)*N);
 for (int i = 0; i < N; ++i)
 {
 a1[i] = rand();
 a2[i] = a1[i];
 a3[i] = a1[i];
 a4[i] = a1[i];
 a5[i] = a1[i];
 a6[i] = a1[i];
 }
 int begin1 = clock();
 InsertSort(a1, N);
 int end1 = clock();
 
 int begin2 = clock();
 ShellSort(a2, N);
 int end2 = clock();
 
 int begin3 = clock();
 SelectSort(a3, N);
 int end3 = clock();
 
 int begin4 = clock();
 HeapSort(a4, N);
 int end4 = clock();
 
 int begin5 = clock();
 QuickSort(a5, 0, N-1);
 int end5 = clock();

 int begin6 = clock();
 MergeSort(a6, N);
 int end6 = clock();
 
 printf("InsertSort:%d\n", end1 - begin1);
 printf("ShellSort:%d\n", end2 - begin2);
 printf("SelectSort:%d\n", end3 - begin3);
 printf("HeapSort:%d\n", end4 - begin4);
 printf("QuickSort:%d\n", end5 - begin5);
 printf("MergeSort:%d\n", end6 - begin6);
 free(a1);
 free(a2);
 free(a3);
 free(a4);
 free(a5);
 free(a6);
}

• 怎么样，从这个运行时间你大概可以看出来吧，单位是毫秒(ms)，不是秒(s)

🌳总结与提炼

今天主要给大家将了插入排序与希尔排序，这是属于插入排序的一种，对于直接插入排序，其时间复杂度是==O(n^2^)==，对于希尔排序，时间复杂度是==O(nlog~2~N)==，我们能从原理到图示再到代码实现，去分析了这两个排序算法，你学会了吗❓