[数据结构与算法]插入、希尔与选择排序

前言

排序在现实生活中无处不在，比如说在某app购物，在搜索到某一商品后，上面的选项有默认排序、按销量排序和按价格排序等等，有了这些排序就可以很方便与快速地让用户找到想要的某一商品，所以排序很重要且无处没有排序。

1. 排序的概念和应用

1.1 概念

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

稳定性：假定在待排序的记录序列中，存在多个具有相同的关键字的记录，若经过排序，这些记录的相对次序保持不变，即在原序列中，r[i]=r[j]，且r[i]在r[j]之前，而在排序后的序列中，r[i]仍在r[j]之前，则称这种排序算法是稳定的；否则称为不稳定的。

内部排序：数据元素全部放在内存中的排序。

外部排序：数据元素太多不能同时放在内存中，根据排序过程的要求不能在内外存之间移动数据的排序。

1.2 应用

最常见的就是购物了。

查看全国大学排名。

等等诸如此类。

1.3 常见的排序

2. 排序算法及实现

排序都默认升序排序

2.1 直接插入排序

2.1.1基本思想

直接插入排序是一种简单的插入排序法，其基本思想是：
把待排序的记录按其关键码值的大小逐个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。

实际中我们玩扑克牌时，就用了插入排序的思想。

通俗点讲就是把一个新的值插入到已经排好的有序数组中，插入完后依然有序。

2.1.2 代码实现

void InsertSort(int* arr, int Size)
{
	for (int i = 0; i < Size - 1; ++i)
	{
		//假设[0, end]之间是有序的
		int end = i;
		
		//插入end+1位置的值
		//因为需要end+1
		//所以外层循环的最大范围在[0, Size-2]
		//如果是到Size-1的位置，+1会越界导致程序崩溃
		//因此外层循环i最大到Size-2
		int tmp = arr[end + 1];
		//循环条件：end是下标要>=0
		//且end位置的值大于tmp
		//不断把比tmp大的数据向后覆盖挪动
		while (end >= 0 && arr[end] > tmp)
		{
			arr[end + 1] = arr[end];
			--end;
		}
		//此时把tmp插入end+1的位置来保持数组有序
		arr[end + 1] = tmp;
	}
}

时间复杂度最坏的情况：O(N2) – 逆序
时间复杂度最好的情况：O(N) – 有序或者接近有序

2.1.3 特性总结

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

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

2.2 希尔排序

直接插入排序的时间复杂度是N2，数据量大就不行了，因此希尔就根据直接插入排序的思想进行了进一步优化提出了接下来介绍的希尔排序。

2.2.1 基本思想

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

希尔排序法的基本思想是：先选定一个整数gap，把待排序数组中所有数据分个组，所有距离差为gap的看作一组，每组进行直接插入排序，只不过跳跃的距离会随着gap的变化而变化，这样的目的是让为了数组接近有序，然后不断缩小gap继续排序，直到让gap为1，当gap=1时，此时的数组已经接近于有序了，然后就相当于整体直接插入排序了。

希尔的效率会比直接插入高吗？

直接插入排序每次交换向前跳一个位置，而希尔排序每次交换会跳gap个位置，因此，当gap越大，越大的数据就会越快地跳到后面，同样的小的数据就会越快的跳到前面。gap越小，跳的越慢但是整体会更接近有序。
就拿逆序的情况来说，直接插入排序第一个位置的值挪到最后一个位置需要挪动N次，而希尔排序只需要N/gap次。

代码实现完后来测试两个排序的效率。

2.2.2 代码实现

void ShellSort(int* a, int n)
{
	//先分成gap组进行预排序
	//目的是让数组接近有序
	//而gap应该如何选取呢？
	//最优方案应该是让gap随着n来变化
	//但是gap最终要落到1
	int gap = n;
	while (gap > 1)
	{
		//可以选择/2或者/3+1
		//两种都会使得gap最终为1
		//gap > 1 -- 预排序
		//gap = 1 -- 插入排序
		gap = gap / 3 + 1;
		//同样的i最大为n-gap-1，否则会越界
		for (int i = 0; i < n - gap; ++i)
		{
			int end = i;
			//假设[0,end]有序
			// 插入end+gap位置的值，使得[0,end+gap]有序
			int tmp = a[end + gap];
			while (end >= 0 && a[end] > tmp)
			{
				a[end + gap] = a[end];
				//每次跳跃gap组
				end -= gap;
			}
			a[end + gap] = tmp;
		}
	}
}

2.2.3 🚀插入 VS 希尔

效率对比：

很遗憾，1000000个数据太大了，直接插入排序我的cpu跑不出来，只能跑出来希尔排序，不过通过上面两个图中的运行时间可以很明显的看出希尔排序的效率比直接插入快太多太多了，两者已经是不在一个量级上的排序了，大概与目前了解过的堆排序是一个级别。

ps：我风扇跑冒烟了

2.2.4 特性总结

1. 希尔排序是对直接插入排序的优化。
2. 当gap > 1时都是预排序，目的是让数组更接近于有序。当gap == 1时，数组已经接近有序的了，这样就会很快。这样整体而言，可以达到优化的效果。
3. 希尔排序的时间复杂度不好计算，因为gap的取值方法很多，导致很难去计算，因此在好些书中给出的希尔排序的时间复杂度都不固定，换句话说我不会，因此直接给结论：时间复杂度大概为O(N^1.3)略低于O(N*logN)。
4. 空间复杂度O(1)。
5. 稳定性：不稳定。

2.3 选择排序

每一次从待排序的数据元素中选出最小（或最大）的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排完 。

堆排序也属于选择排序，在堆的应用这篇文章中详细介绍了堆排的实现，这里就不再介绍。

2.3.1基本思想

在元素集合array[i]–array[n-1]中选择关键码最大(小)的数据元素。
若它不是这组元素中的最后一个(第一个)元素，则将它与这组元素中的最后一个(第一个)元素交换在剩余的array[i]–array[n-2] (array[i+1]–array[n-1])集合中，重复上述步骤，直到集合剩余1个元素。

简言之：遍历一遍选出最小的放在最左边0下标的位置，在遍历一边选出次小的，放在1下标的位置…依次重复以上操作。

2.3.2代码实现

在实现的时候可以稍微优化一下：遍历一次可以同时选出最大的和最小的两个数，最小的放左边，最大的放右边。

void SelectSort(int* a, int n)
{
	int left = 0;
	int right = n - 1;
	while (left < right)
	{ 	
		//一趟选出最大和最小的
		int mini = left;
		int maxi = left;
		//选出来后需要进行交换
		//因此mini和maxi是对应的下标而不是对应的值
		for (int i = left + 1; i <= right; ++i)
		{
			if (a[mini] > a[i])
				mini = i; 	
			if (a[maxi] < a[i])
				maxi = i;
		}
		//最小的放最左边
		Swap(&a[left], &a[mini]);
		//如果left = maxi
		//当left和mini交换后maxi位置的值就不是原来left位置的值了
		//因此需要把maxi赋值为新的maxi的位置
		//即mini的位置
		//比如说：[4，2，1，3]
		//maxi是0，mini是2
		//left和mini交换后：[1，2，4，3]
		//此时maxi为0对应的值就不对了
		//因此需要更新maxi为mini
		if (left == maxi)
			maxi = mini;
		//最大的放最右边
		Swap(&a[right], &a[maxi]);
		++left;
		--right;
	}
}

很明显这是一个O(N2)的排序，并且最好的情况下也是O(N2)，因为数组中的数据无论什么状态都不会影响到它，不管是否有序都要遍历一遍，可以说是最烂的排序之一。

2.3.3 特性总结

直接选择排序的特性总结：

1. 直接选择排序思考非常好理解，但是效率不是很好。实际中很少使用
2. 时间复杂度：O(N^2)
3. 空间复杂度：O(1)
4. 稳定性：不稳定

3. 冒泡、插入与选择排序测试

到目前为止学到过时间复杂度为O(N2)的排序有如上三种，那么三种的复杂度相等，效率也相等吗？接下来就来比较一下三个排序的效率，看看哪个效率最高。
测试之前先把冒泡排序的代码附上，思想很简单，这里也不介绍了，大伙应该都能手撕吧。

代码：

// 冒泡排序
void BubbleSort(int* a, int n)
{
	for (int i = 0; i < n - 1; ++i)
	{
		//加个小优化
		int flag = 1;
		for (int j = 0; j < n - 1 - i; ++j)
		{
			if (a[j] > a[j + 1])
			{
				Swap(&a[j], &a[j + 1]);
				flag = 0;
			}
		}
		if(flag)
			break;
	}
}

开始比较：

两分钟后~

再大一点就没必要再测了，不难看出冒泡的效率比选择排序更低，可以说冒泡是第二烂的排序了，因为相比于选择排序，冒泡有一个优势是在接近有序或者有序的情况下效率是比选择排序快的多的，因为选择排序无论如何都要一次次遍历。

相比较而言，直接插入排序的效率是最高的，也可以说插入排序是在O(N2)中很不错的排序算法了。

总结

本文主要介绍了几个简单排序，后面还有快速排序和归并排序等更优秀的排序等着。