1.什么是插入排序
直接插入排序是一种简单的插入排序法，其基本思想是：把待排序的记录按其关键码值的大小逐 个插入到一个已经排好序的有序序列中，直到所有的记录插入完为止，得到一个新的有序序列 。 实际中我们玩扑克牌时，就用了插入排序的思想
2.插入排序有啥用
插入排序有以下几个用途：
对于少量元素的排序，它是一个有效的算法
对于已经接近排好序的数组，它的效率很高，时间复杂度为 O (N)
它可以作为其他复杂排序算法的一部分，例如快速排序
插入排序的精髓在于设置一个有序的空数组在它为空的时候就认定它为有序数组，并在不断插入的过程中维护其有序性，所以，我们实际上一直在干的事就是向一个有序数组中不断插入新元素，这比直接进行排序的操作手法要简单的多
3.插入算法的实现
当插入第i(i>=1)个元素时，前面的array[0],array[1],…,array[i-1]已经排好序，此时用array[i]的排 序码与array[i-1],array[i-2],…的排序码顺序进行比较，找到插入位置即将array[i]插入，原来位置 上的元素顺序后移
具体代码实现
//直接插入排序 void InsertSort(int* a, int n)//a是数组首元素地址，n是数组元素个数 { //[0-end]有序，end+1位置插进去，让[0-end+1]也有序 int i = 0; int end = 0; for (i = 0; i < n - 1; i++)//对n个数进行排序，一共需要排n-1次 { end = i;//下标标志end随着i的变化而变化 int tmp = a[end + 1];//用tmp保存end+1位置的值，防止后面交换时丢失 while (end >= 0) { if (a[end] > tmp) { a[end + 1] = a[end];//把a[end]赋给a[end+1](把较大值赋给较小值)(让较大值代替较小值) end--;//下标标志end-1;进行下一次循环，继续比较前两个数的值(a[end]和a[end+1])， //直到end == -1,不再进入循环 } else//如果tmp大于a[end]，则跳出循环，执行下一个for循环 { break; } } a[end + 1] = tmp;//循环完之后，将--后的end再+1的位置换成tmp,就实现了(end+1位置插进去，让[0-end+1]也有序) //如果循环完之后end没有--，则end+1位置还是tmp } //两个循环结束后，就排好了 }
4.总结
- 元素集合越接近有序，直接插入排序算法的时间效率越高
- 时间复杂度：O(N^2)
- 空间复杂度：O(1)，它是一种稳定的排序算法
- 稳定性：稳定
