目录

• 直接插入排序
• 1.基本思想
• 2.算法实现
• 3.时间复杂度

插入排序分为两种：直接插入排序&希尔排序

直接插入排序

1.基本思想

直接插入排序是一种简单的插入排序算法，其基本思想是：

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

说得通俗一点就是：

假设区间[0, end]有序，将end+1位置的值插入到[0, end]中，保持区间[0, end+1]依旧有序。

生活中我们玩*牌时，就用了插入排序的思想。

在这里，我们以排升序为例。

核心思想：摸牌的过程

动图演示：

2.算法实现

写排序时，先从单趟开始考虑

//[0, end]已经有序，将end+1位置的值插入到[0,end]中，使得[0,end+1]依旧保持有序
//有一个有序区间，插入一个数据，依旧保持有序
void InsertSort(int* a, int n)
{
	for (int i = 0; i < n - 1; i++)
	//控制摸牌的过程，一开始从仅一张开始
	//注意循环结束条件，只需要到n-2的位置，若将其改成i<n，则会出现越界的情况
	{
		int end = i;
		int tmp = a[end + 1];
		while (end >= 0)//保证牌是有序的
		{
			if (a[end] > tmp)
			{
				a[end + 1] = a[end];//往后挪，注意画图感受哦
				end--;
			}
			else
			//有两种可能：（现想常规的，再考虑特殊情况）
			//一是找到了比它小的数，放到其后；
			//二是没有比它小的数，直到end为-1才结束
			{
				break;
			}
		}
		a[end + 1] = tmp;
	}
}

完整代码：

3.时间复杂度

直接插入排序时间复杂度是O(N^2)，注意哦，不是因为双重循环，需要实际计算来得出时间复杂度。

最坏情况：逆序有序，1+2+3+……+n - 1；O(N^2)

最好情况：顺序有序，1+1+1+……+1。O(N)