插入排序，又叫直接插入排序。实际中，我们玩扑克牌的时候，就用了插入排序的思想。
基本思想：
在待排序的元素中，假设前n-1个元素已有序，现将第n个元素插入到前面已经排好的序列中，使得前n个元素有序。按照此法对所有元素进行插入，直到整个序列有序。
但我们并不能确定待排元素中究竟哪一部分是有序的，所以我们一开始只能认为第一个元素是有序的，依次将其后面的元素插入到这个有序序列中来，直到整个序列有序为止。
代码如下：
//插入排序void InsertSort(int* a, int n){ int i = 0; for (i = 0; i < n - 1; i++) { int end = i;//记录有序序列的最后一个元素的下标 int tmp = a[end + 1];//待插入的元素 while (end >= 0) { if (tmp < a[end])//还需继续比较 { a[end + 1] = a[end]; end--; } else//找到应插入的位置 { break; } } a[end + 1] = tmp; //代码执行到此位置有两种情况: //1.待插入元素找到应插入位置（break跳出循环到此）。 //2.待插入元素比当前有序序列中的所有元素都小（while循环结束后到此）。 }}
