插入排序：有n个数，第i个数前面都是有序的话，那么i插入到排好的系列中就非常简单，和前面的数一一比较就ok了，对于一个序列，那么从第二个数开始和前面数比较，排好前面2个数之后来把第三个数插入到前面2个数中就非常简单了，第四个数亦是如此，以此类推.....................

#include<iostream>
#include<vector>
using namespace std;


//void insert_sort(vector<int> &a)
//{
//	int temp;
//	size_t n = a.size();
//	for ( int i= 1; i < n; i++)
//	{
//		for (int j = i - 1; j >= 0 && a[j]>a[j + 1]; j--)
//		{
//			temp = a[j];
//			a[j] = a[j + 1];
//			a[j+ 1] = temp;
//		}
//	}
//}

void insert_sort2(vector<int> &a)
{
	int temp;
	size_t n = a.size();
	for (int i = 1; i < n; i++)
	{
		for (int j = i - 1; j >= 0; j--)
		{
			if (a[j]>a[j + 1])
			{
				temp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = temp;
			}
		}
	}
}



int main()
{
	vector<int> a = { 5,9, 77, 56, 6, 8, 1, 5,100 };
	insert_sort2(a);
	for (const auto i : a)
		cout << i << " " << endl;

	return 0;
}

插入排序之算法研究