【数据结构】插入排序

前言

排序皆以升序为例进行讲解

直接插入排序（插排）

生活样例 —— 我们玩扑克牌就是运用了插入排序的思想

一、图例演示

☆二、核心算法思路

从第2个开始，前面只有1个，只有1个就是有序。

把待排序的记录按其关键码值的大小逐个插入到一个 已经排好序的有序序列 中，直到所有的记录插入完为止，得到一个新的有序序列 。

三、算法思路步骤

升序降序同理

• 单趟

1. end=0，指向第1个位置（1个也是有序），从第一个开始，将前面的数字都排成有序，已确保前方都是 已经排好序的有序序列
   
2. end指向的是 序列中已经排好序 的部分的末端
   
3. tmp先存储好 a[end+1] ( a[end+1]是要进行插入到前方有序序列的数据 ) ，避免与前面的数据进行比较后 后移，该节点的数据被覆盖。
   
4. end其后一个数据end+1 向前比较，若 后小于前，则将前面的后移覆盖【也正是因为是 从前往后排 => 前面的数据是已经排好序的有序 => 比它大的都在后面 都往后移】同时end --，进行向前比较遍历。
   
5. 遇到比它小的就停下，在a[end+1]的位置 将tmp赋值给a[end+1]（因为在整体中是在比较判断外面进行的 end–， 所以不管是否进行后移，都会end–，所以要+回1）
   

• 整体
  就用 for(i=0; i<n-1(end到倒数第二个，end+1就是最后一个要进行插排的数了) ；i++) 循环，i 记录控制 end每轮单趟插排所在的 序列中已经排好序 的部分的末端。

【注意好这里有 i<n-1 的意义！！控制下标边界问题！！】

四、码源解析

• 插入排序 —— 单趟

//单趟
void InsertSort(DataType* a, int n) {
  int end = n - 1;
  DataType tmp = a[end];
  while (end > 0) {
    if (tmp < a[end - 1]) {
      a[end] = a[end - 1];
      end--;        //是出循环的条件，别忘了
    }
    else
      break;        //有tmp比所有值都小的情况，则进入了if(tmp < a[end - 1])的条件没有办法出来
  }
  a[end] = tmp;       //将这个单独拎出来
}

• 插入排序 ——整体

//插入排序 —— 整体  //插入排序：是从前往后，一个一个往前对比遍历排
void InsertSort(DataType* a, int n) {
  for (int i = 0; i < n-1; i++) {
    int end = i;
  DataType tmp = a[end + 1];       //先将要移的数先保存起来，前面发生挪动会将其覆盖
  while (end >= 0) {   //错误示范while (end > 0)，那么第一个end=i=0时，进不去while循环 所以要 >=
    if (a[end] > tmp) {
      a[end+1] = a[end];        //比tmp大的都向后挪一位
    }
    else {         //遇到比tmp要小的就停下来，插入tmp
      break;      //有tmp比所有值都小的情况，则进入了if(a[end] > tmp)的条件 没有办法走到else里将tmp赋值给a[end+1]，所以把a[end+1] = tmp;放在else里 会在tmp比所有值都小的情况下失效
    }
    --end;        //这里--了后面要+1 （--就到了空出的位置的前一个）
  }   
  a[end+1] = tmp;       //将这个单独拎出来
    }
}

注意点：

1. a[end+1] = tmp;单独拎出来，为了避免 tmp比所有值都小的情况，则进入了if(a[end] > tmp)的条件 没有办法走到else里将tmp赋值给a[end+1]，所以把a[end+1] = tmp;放在else里 会在tmp比所有值都小的情况下失效
2. 该算法的核心 操纵的是下标，而不是节点本身
3. 下标边界问题：end 指向有序序列部分的末端，则end+1则是要进行向前比较插入的待排序的数据 ，数组是[0,n-1], end遍历到n-2就已经是最大了，则end+1 则是要进行向前比较插入的待排序的最后一个数据 为n-1。

五、效率分析

1. 时间复杂度

最坏：O（N^2）降序逆序

最好：O（N） 顺序有序

2. 空间复杂度

算法在执行过程中，只有 「移动」变量 时候，需要事先将变量存入临时变量x，而其它没有采用任何的额外空间，所以空间复杂度为 O ( 1 )

与冒泡排序进行对比（同样是小数据排序）：冒泡 < 插排

排前面都有序，就最后两个数字顺序颠倒

进行比较的次数

• 冒泡：n-1 [进行第一次遍历] + n-2 [第一次遍历排好后，再进行第二次遍历检查一遍，排好了结束]
• 插排：n-1 [从头开始遍历比较一遍] + 1 [多插一次]

得出结论：

时间复杂度上 O（N）一样

空间复杂度上O（1）也一样

但在细节上，局部有序，有一小段有序，插排的情况都会好很多，中间挪动次数也会少很多