【数据结构】直接插入排序

目录

一、基本思想

二、动图演示

三、思路分析

四、代码实现

五、易错提醒

六、时间复杂度分析

一、基本思想

直接插入排序（Straight Insertion Sort）是一种简单直观的排序算法，其基本思想是：

把待排序的一个记录按其关键码值的大小，从后往前扫描，插入到一个已经排好的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列。

生活中我们玩扑克牌以及整理书籍的时候都用到了直接插入排序算法的思想。

二、动图演示

三、思路分析

这里以升序为例：

1. 首先要从无序表中取出第一个元素a，确定a的位置序号，跟有序表中最后一个元素进行比较
2. 若发现a小于有序表的最后一个元素，则将有序表的最后一个元素放在元素a的位置（这里要先将a用临时变量tmp存放起来，防止被覆盖）
3. 然后再让tmp与有序表倒数第二个元素进行比较，以此类推......
4. 当a不小于有序表中的某个元素时，则将a放在该元素的下一个位置即可
5. 这样就完成了单趟的排序，下一个无序表中的元素重复相同步骤

结合图分析，如下所示：

四、代码实现

下面是升序代码的实现

//n为数据元素个数
void InsertSort(int*a,int n)
{
	for (int i=0;i<n-1;i++)//这里i从下标位置为0的开始
	{
		//单趟排序
		//[0,end]的值有序，end+1处的值插入[0，end]，仍保持有序
	int end = i;
	int tmp = a[end+1];

	while (end>=0)
	{
		if (tmp < a[end]) //注意这里的tmp不能换成a[end+1],因为之前的a[end+1]会被覆盖
		{
			a[end + 1] = a[end];
			end--;
		}
		else
		{
			break;
		}
	}
	a[end + 1] = tmp;
	}
}

五、易错提醒

为什么要将a[end+1]=tmp写在while循环外面呢？而不是写在else语句里呢？

分析如下：

因为这里会出现两种情况

情况1：当待排的数字不比有序序列的第一个元素小的时候，那就可以将a[end+1]=tmp;写在else语句里

情况2：当待排的数字比有序序列的第一个元素小的时候，也就是如下图情况：

经过上图分析可知，我们其实可以将代码写成如下形式：

void InsertSort(int* a, int n)
{
	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
			{
				a[end + 1] = tmp;
				break;
			}
		}
		if (end == -1)
		{
			a[end + 1] = tmp;
		}
	}
}

 该代码是把情况1和情况2分开来写，这种写法更易于理解

而将a[end+1]=tmp写在while循环外面是把两种情况写在了一起，使得代码更加简洁高效。

六、时间复杂度分析

最好情况下的时间复杂度是：O(N)

最坏情况下的时间复杂度是：O(N^2)

分析过程如下图所示：