本文共 686 字，大约阅读时间需要 2 分钟。

• 思想

插入排序(Insertion Sorting)的基本思想是:把 n 个待排序的元素看成为一个有序表和一个无序表，开始时有序表中只包含一个元素，无序表中包含有 n-1 个元素，排序过程中每次从无序表中取出第一个元素，把它的排序码依次与有序表元素的排序码进行比较，将它插入到有序表中的适当位置，使之成为新的有序表。

• 图解

先将第一个元素看作是有序的，比如5，然后从后边无序的序列中取出一个2与之对比，2小于5，交换位置，形成有序序列 2 5，从无序序列中取出4与有序序列对比，大于 2 小于 5，插入2和5之间，形成新的有序序列，再从无序序列中取出6，插入有序序列 2 4 5，形成有序序列 2 4 5 6，从无序序列中取出1，插入有序序列形成 2 3 4 5 6，最后从无序序列中取出 1，插入有序序列形成 1 2 3 4 5 6 有序序列。

• 代码

void InsertSort(int* a, int n){
   	// 控制end的位置从0走到n-2	for (int i = 0; i < n - 1; ++i)	{
   		// 单趟排序		// 在[0,end]区间中插入tmp，依旧有序		int end = i;		int tmp = a[end + 1];		while (end >= 0)		{
   			if (a[end] > tmp)			{
   				a[end + 1] = a[end];				--end;			}			else			{
   				break;			}		}		a[end + 1] = tmp;	}}

转载地址：http://lqwzi.baihongyu.com/