1. 简介

插入排序，也称为直接插入排序，其排序思想和我们平时打扑克牌时排序类似。

2. 算法步骤

1. 在下面的动画中，柱子表示一个个的数字，数字越大，柱子越高。

2. 左边的柱子标注为橙色，表示有序的数字，右边浅蓝色的柱子表示还没进行排序的数字。一开始，把第 1 个元素看作已经有序的序列，第 2 到第 n 个个匀速为无序序列。

3. 每一轮都是把右边一个无序的数字插入到左边有序的数里。因为左边的数字本身已经有序，找位置插入的原则是：从后往前找，找到第一个小于等于要插入的这个数字的数字，插到这个数字的后面。

4. 插入数字的时候，要挪动这个位置及后面的数字，让出一个空位置出来。这个挪动的动作是插入排序很重要的工作开销。如果之前的数字就大致有序，那么挪动的情况就少。如果之前的数字非常杂乱无章，挪动的情况就多。最终排序的时间和原本数字的情况有关，所以，我们说插入排序是一种不稳定的排序算法。

5. 一开始，全部数字都是未经排序的。然后，有序的数字逐渐增加（橙色的柱子多起来），无序的数字减少。最后，全部数字都称为有序数字（都称为橙色的柱子）。

3. 效果图：

4. 代码模板

#include<bits/stdc++.h>
using namespace std;
int x[10001];
int main(){
    int n;
    cin>>n;

    for(int i=1;i<=n;i++)
    	cin>>x[i]; //数字输入到 x 数组 ,一开始是无序的 

	int tmp,p; // 有序的数字位于 [l,R] 最开始是 [1,1]，x[1] 只有 1 个数，我们认为它就是有序的 
	
	for(int i=2;i<=n;i++) // 把 x[2] 到 x[n] 插入到 x[1],x[2],...,x[i-1], 
	{
		for(p=i-1;p>0;p--)
			if(x[p]<=x[i]) break; //找到插入的位置
			 
		//x[p]<=x[i]，所以，x[i]应该 插入到 x[p] 后面
		 
		tmp = x[i]; //记录下 x[i]是什么 
		for(int j=i-1;j>=p;j--) //从 x[p] 到 x[i-1] 全部往后挪一个位置 
			x[j+1] = x[j];
		x[p]=tmp; //x[p] 保存要插入的数字 
	}
 
	for(int i=1;i<=n;i++) //输出有序的数字 
		cout<<x[i]<<" "; 
 
    return 0;
}

同样的意思，可以改一下，这样写：

#include<bits/stdc++.h>
using namespace std;
int x[10001];
int main(){
    int n;
    cin>>n;

    for(int i=1;i<=n;i++)
    	cin>>x[i]; //数字输入到 x 数组 ,一开始是无序的 

	int tmp,p; // 有序的数字位于 [l,R] 最开始是 [1,1]，x[1] 只有 1 个数，我们认为它就是有序的 
	
	for(int i=2;i<=n;i++) // 把 x[2] 到 x[n] 插入到 x[1],x[2],...,x[i-1], 
	{
		if(x[i]<x[i-1]) //x[1] 到 x[i-1] 是有序的，x[i-1] 是当中最大的。如果 x[i] 比 x[i-1] 大，那么 x[i] 就是插入到 x[i-1] 后面，就是什么都不用做了 
		{
			for(p=i-1;p>0;p--)
				if(x[p]<=x[i]) break; //找到插入的位置
				 
			//x[p]<=x[i]，所以，x[i]应该 插入到 x[p] 后面
			 
			tmp = x[i]; //记录下 x[i]是什么 
			for(int j=i-1;j>=p;j--) //从 x[p] 到 x[i-1] 全部往后挪一个位置 
				x[j+1] = x[j];
			x[p]=tmp; //x[p] 保存要插入的数字 			
		}
	}
 
	for(int i=1;i<=n;i++) //输出有序的数字 
		cout<<x[i]<<" "; 
 
    return 0;
}

5. 稳定性

如果有两个数据元素他们的关键特性是一致的（例如按照大小排序的时候，两个一样大的数字就是具有相同的关键特性），排序前和排序后这两个数据的位置发生了变化，那么我们认为这个排序算法就是不稳定的。

按照上面的代码，插入排序是稳定的。

6. 计算复杂度

假设 x[ ] 数组在排序之前就已经是有序的，x[i] <= x[i+1] ，那么运行上面这个程序就压根没有触发数据插入的那段代码。整个程序就是比较了 n-1 次就完成了比较。

这个问题也是比赛理论题的一个高频考点，就问你数据有序的情况下，插入排序比较了多少次完成排序，答案就是 n-1 。

如果数据一开始是反序的，那么每一次 x[i] 都是插入到 x[1] 的位置，那么计算复杂度就是 O(n^2).