插入排序

最近会把各种排序都做一个总结，总觉得写后台没什么意思，那就先复习复习算法吧

相信大家对于插入排序肯定不会陌生了，它适合于少量数据的排序，时间复杂度为O（n^2），空间复杂度为O（1）（记录插入的数据 ）

从某种程度上来讲要优于冒泡排序

下面简单的介绍一下插入排序算法的核心思想：

这种算法是基于递归思想的，要将[0..n-1]这个数组进行排序

先假设对于较小数组[0..n-2]的排序已经解决，从右往左的扫描这个数组，如果遇见的第一个小于或等于A[n]的元素，就把A[n]放在这个元素的后面

代码如下

for（int i=1;i++;i<n）
  {
    int v=i;
    int j=i-1;
    while(j>0){
      if(a[j]>v){
        a[j+1]=a[j];
        j--;
        }
      a[j+1]=v;
     }
  }

分析一下时间复杂度

在最坏情况下a[j]>v的的执行次数会达到最大，也就是每个j都要执行一次

所以比较次数是：n(n-1)/2

插入排序的优势

对无序元素对的分析得知，这种排序的平均比较次数是是n^2/4

而这个数据在遇到基本有序数组的时候会更小，这让它优于其他的两个竞争对手：选择排序和冒泡排序