【数据结构与算法】第10课—数据结构之插入排序

1. 排序

  什么是排序？所谓排序，就是使用一串记录，按照其中的某个字或或某些关键字来对其进行递增或递减式的排列。
  简单通俗点讲，就像我们在淘宝页面，所有商品我们可以让他按照价格排序，也可以按照销售量排序等，排序在我们生活中随处可见。

• 这张图片就是我的博客按照时间顺序来进行排序的，还麻烦各位兄弟姐妹路过时点个赞奥！

2. 排序算法

  那么常见的排序算法都有哪些呢？接下来一张图来带大家了解

• 今天呢，我们先来学习第一种排序算法—插入排序

3. 插入排序

• 插入排序呢，又分为两种：直接插入排序和希尔排序，接下来我们直入主题

3.1 直接插入排序

• 那什么是直接插入排序呢？

• 相信大家都玩过扑克牌吧，其实玩扑克牌的过程就应用了直接插入排序的思想，在拿到牌的时候，是不是每次都要对比一下手里已经排好顺序的手牌，然后再将拿到的牌按照顺序插入其中，没错，直接插入排序的思想如出一辙

• 直接插入排序的思想就是从头开始排序，拿到新的元素与之前已经排好序的序列对比，然后将它放到合适的位置，再拿新的元素与已经排好序的序列对比，插入和合适的位置，以此往复，直到所有都插入完毕结束

  接下来我将用图解的方式来帮助大家去理解





  通过上述图解我们可以看出直接插入排序的过程，每趟对比arr[end]和tmp，如果arr[end]大，那么就要赋值，再让end–，再对比arr[end]和tmp，以此往复，就可以完成排序

• 那么接下来我们看看代码如何实现

//直接插入排序
void InsertSort(int* arr, int sz)
{
	int i = 0;//排序的趟数
	for (i = 0; i < sz - 1; i++)//由于排序的趟数 = 数组元素-1，数组下标是从0开始的，则i<sz-1
	{
		int end = i;//已排好序的序列尾元素下标
		int tmp = arr[end + 1];//已排好序的尾元素后面那个元素(每趟)
		while (end >= 0) //end不越界进入循环
		{
			if (arr[end] > tmp)
			{
				arr[end + 1] = arr[end];
				end--;
			}
			//如果tmp > arr[end]
			else
			{
				break;
			}
		}
		//此时已经对比完
		arr[end + 1] = tmp;
	}
}

3.1 希尔排序

  通过上述直接插入排序我们可以看出，如果数组arr是有序(降序)的，那么它的时间复杂度就是O(n^2),这也是它最坏的情况，如果数组arr是有序(升序)的，那么它的时间复杂度是O(n),它只用每趟对比，不用赋值交换
  那么如何可以降低它的时间复杂度呢？这时候就提出了希尔排序

• 希尔排序的算法思想是先选定一个整数(通常呢是gap=n/3+1)，然后把待排序的数组分为三组进行直接插入排序，然后再让gap=gap/3+1得到下一个整数，按照这个整数再进行分组，直接插入排序，当gap=1时，相当于直接插入排序
• 它是在直接插入排序算法的基础上改进的，自然效率要比直接插入要好点

  接下来来我们来看看它是怎么实现的吧

  接下来让我们看看代码是如何实现的吧

• 代码

//希尔排序
void ShellSort(int* arr, int sz)
{
	int gap = sz;
	while (gap > 1)
	{
		gap = gap / 3 + 1;
		for (int i = 0; i < sz - gap; i++)
		{
			int end = i;
			int tmp = arr[end + gap];//初始时tmp在end+gap的位置
			while (end >= 0)
			{
				//如果arr[end]大于tmp
				if (arr[end] > tmp)
				{
					arr[end + gap] = arr[end];//让arr[end+tmp]等于arr[end]
					end = end - gap;//因为分组，end不再--，而是走到end-gap的位置
				}
				else
				{
					break;
				}
			}
			arr[end + gap] = tmp;//最后end+gap的位置要将tmp的值放进来
		}
	}
}

  这里为什么让gap=gap/3+1呢？因为如果gap除的数大了，那么分的组少，对比的次数也多；而gap除的数小了，分的组少，每组对比的次数少，所以一般取gap=gap/3+1或者gap=gap/2+1

4. 插入排序时间复杂度和空间复杂度

• 直接插入排序的时间复杂度是O(N^2)，空间复杂度是O(1)
• 希尔排序的时间复杂度一直存在着争论，因为希尔排序中用到的gap值不确定，这就导致它的时间复杂度存在不确定性，不过目前经过大量实验证明，希尔排序的时间复杂度约为O(n^1.3)

  由于直接插入排序的时间复杂度较高，因此它并不是一个好的排序算法，常常用来作为教学