数据结构 — 插入排序
插入排序
基本思想
其实好多人总是分不清插入排序和冒泡排序，更有甚者一直就是一口咬定看到插入喊冒泡，看到冒泡还喊冒泡.这我就
很尴尬了 今 天 呢我们先来瞧瞧这个插入排序，相信冒泡排序大家都懂所以这里就不说了，直接开始主题.
插入排序：每次将一个待排序的记录，按其关键字大小插入到前面已经排好序的子序列中的适当位置，直到全部记录
插入完成为止 其实插入排序在我这里看来还是不够直观，我觉得就应该叫他挖坑—插入排序. 为什么我要起这样的名字
，这是因为是先挖坑再元素 插 入到坑里，那么具体的过程我们来看一看.
也就是当你循环走到a[i]这个位置时，前面的a[0]....a[i-1]都已经依次排好序了，因为该过程是从a[0]开始，每遇
到一个元素就 执行一次该过程，所以当循环走完最后一个元素，那么该插入排序完成. 有木有觉得突然就想明白了.
代码实现
void Insertsort(int arg[], int n)
{assert(arg != NULL);int i = 0;int j = 0;int tmp = 0;for (; i < n; i++){tmp = arg[i];j = i - 1;while (j >= 0 && arg[j] > tmp){arg[j + 1] = arg[j];j--;}arg[j + 1] = tmp;}
}
void Insertsort2(int a[], int n)
{ int i, j; for (i = 1; i < n; i++) if (a[i] < a[i - 1]) { int temp = a[i]; for (j = i - 1; j >= 0 && a[j] > temp; j--) a[j + 1] = a[j]; a[j + 1] = temp; }
}
总结
我们现在很清楚的明白了插入排序的过程，他不同于冒泡排序或者说更优于冒泡排序，接下来看他们之间的区别:
算法名称 最差时间复杂度 平均时间复杂度 最优时间复杂度 空间复杂度 稳定性
冒泡排序 O(N^2) O(N^2) O(N) O(1) 稳定
插入排序 O(N^2) O(N^2) O(N) O(1) 稳定
从上面看就是一模一样的对吧... 我们通俗一点讲，比如最近个个大学都在新生军训有一名新生叫小卷，他早上迟到了
，当它来到 自己的部队的时候自己的同学都已经站好队，在哪里站军姿，这时候小卷做完教官罚他的俯卧撑归队，(假设
队伍按大小个排队) 这是小卷使用 冒泡排序 来寻找自己的位置，从该排的排头开始跟第一名同学比较如果我比你高那么我
们就交换小卷就一直用这种方 式寻找自己的位置，但是这一排有100个 同学，而小卷是最高的.这时候教官生气了就喊小卷
你再过来做50个俯卧撑直接滚去最后一 列，很明显教官使用的就是 插入排序 . 希望大家以后分辨清楚插入排序和冒泡排
序，只有明白各自的原理呢，就能分清两个概念.
当然冒泡排序也会有优化的算法，比如当你这个区间有序我就不用进去交换循环，直接跳到下一个循环.这个时候冒泡的时
间复杂度最坏的位O(N^2)最好的时间复杂度为O(N), 那么如果有人问你冒泡和插入排序什么区别，如果让你使用你会用哪一
个.并且告诉我为什么??? 这个时候，不用担心我选择的依旧是插入排序. 因为冒泡排序的优化需要的是严格的有序.它才能
跳过这次循环查找. 而插入排序是如果你近似有序我依然可以让它少循环很多次，所以效率从这里会有一点微弱的不同.
