插入排序法

1. 算法步骤
将第一待排序序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。

从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）
2.时间复杂度分析
最好情况是需要排序的序列基本有序，序列是递增的。这样的时间复杂度是O(n),最坏的情况是序列是递减的。这样的时间复杂度是O(n^2)

#include<iostream>
using namespace std;
int main()
{
	int a[10];
	int n;
	int j;
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i];    // 61 17 29 22 34 60 72 21 50 62 
	//插入排序
	for (int i = 1; i < n; i++)
	{
		int temp = a[i];
		j = i - 1;
		while (j >= 0 && temp < a[j])
		{
			a[j + 1] = a[j];
			j--;
		}
		a[j + 1] = temp;
	}
	for (int i = 0; i < n; i++)
		cout << a[i] << " ";
}