插入排序（Insert sort）

1. 思想：
   第1轮：把第一个元素看作有序的， 读取第二个元素，将其插入到左边的有序序列中；
   第2轮：左边两个元素有序，读取第三个元素，将其插入到左边的有序序列中； ……
   第n-1轮，左边n-1个元素有序，读取第n个元素，将其插入
2. 优缺点：稳定、但是效率低下
3. 复杂度：
   不需要额外的辅助空间，空间复杂度为O(1)
   平均时间复杂度：O(n^2)、最好(数组有序)：O(n)、最差(正好倒序)：O(n ^2)
4. 稳定性：稳定

源代码

/************************************
 题目：插入排序
	每轮都把后面的一个数插入前面的有序序列中
*************************************/
#include<iostream>
using namespace std;

//参数：
//		numbers[]：数组
//		length：数组长度
void Insert_Sort(int numbers[], int length)
{
	//1. 判断传入参数是否有效
	if (numbers == nullptr || length <= 0)
		return;
	
	int j;
	int temp;	//临时变量

	//2. 外层循环代表轮次，每轮的结果都是：将后面的数插入前面的有序序列中
	for (int i = 1; i < length; ++i)
	{
		//3. 获取有序序列后面的一个元素作为要插入的元素
		temp = numbers[i];
		//4. 内层循环完成元素的移动（当数列有序时，内层循环只运行一次就break了，总的时间复杂度就会变成O(n)
		for (j = i - 1; j >= 0; --j)
		{
			//5. 如果要插入的元素大于或等于有序序列中的某一个元素，说明要插入的元素的位置就在这个元素后面
			if (numbers[j] <= temp)	//等号能保证稳定性
				break;

			//6. 未找到插入位置则将元素依次往后移动
			numbers[j + 1] = numbers[j];
		}
		//7. 将要插入的元素放在找到的位置
		numbers[j + 1] = temp;
	}
}
//简单测试
int main(int argc, char* argv[])
{
	const int length = 7;
	int numbers[length] = { 3, 2, 7, 11, 9, 4, 2 };	

	Insert_Sort(numbers, length);

	for (int i = 0; i < length; i++)
		cout << numbers[i] << "  ";

	cout << endl;
	return 0;
}

仍有不足，欢迎交流。