直接插入排序

一、算法介绍

1.排序思想

直接插入排序的排序思想是将集合内元素直接对已经有序的序列（默认集合内的第一个元素为初始有序序列）进行遍历比较，然后直接插入到相应位置，插入位置之后的元素顺序后移一位，经过n-1趟插入完成排序。

2.算法流程

比如给定一个数组为arr[]={5,8,4,1,2,6,0,3,7,10,9}，那么默认初始有序序列就是（5），待排序序列就是（8,4,1,2,6,0,3,7,10,9），其排序流程如下：

3.改进思路

根据直接插入排序算法的原理可知，算法的时间主要耗费在了寻找元素待插入位置上了，如果能够将这部分时间给降下来，那么就可以有效的提高算法的效率。

结合直接插入排序的主要应用场景就是在序列本身基本有序的情况下，算法在查找待插入位置时能够进行较少次数的比较和元素搬移操作，所以我们就可以通过一些方法来将序列调到基本有序的状态，这样就能提高算法的效率，由前辈设计出了希尔排序，具体算法思想和实现可以参考博文。

二、算法实现

1.代码实现

#include<iostream>
using namespace std;
void InsertSort(int* arr, int size) {
  for (int i = 1; i < size; i++) {//从1开始循环，默认第一个元素为有序序列
  int end = i - 1;//标记有序序列末尾位置下标
  int key = arr[i];//标记待插入元素
  while (end >= 0 && key < arr[end]) {//key从有序序列从后往前比较
    arr[end + 1] = arr[end];//往后搬移
    end--;
  }
  //key大于等于当前元素，找到插入位置，跳出循环
  arr[end + 1] = key;//将key插入到当前元素之后
  }
}
void PrintArray(int* arr, int size) {//数组打印函数
  for (int i = 0; i < size; i++) {
  cout << arr[i] << ' ';
  }
  cout << endl;
}
void Test() {
  int arr[] = { 5,8,4,1,2,6,0,3,7,10,9 };
  int size = sizeof(arr) / sizeof(arr[0]);
  cout << "排序前：";
  PrintArray(arr, size);
  InsertSort(arr, size);
  cout << endl << "排序后：";
  PrintArray(arr, size);
}
int main() {
  Test();
  return 0;
}

2.测试用例及结果

用例1：arr[]={5,8,4,1,2,6,0,3,7,10,9}

结果：

用例2：arr[]={15,42,15,96,2,3,4,25,45}

结果：

三、性能分析

1.时间复杂度

最坏情况：

如果初始集合内元素恰好是排序要求相逆的次序，那么每次插入都需要完整的遍历一遍有序序列才能找到待插入位置。此情况下while循环内的代码将被执行 次，因为时间复杂度计算只关心最终的量级，所以最坏情况下时间复杂度为O（ ）。

最好情况：

若集合内元素初始本身就是符合待排序要求有序的情况，那么每次插入都只需要进行一次比较就可以完成，那么循环内的代码就只需执行n-1次，所以最好情况下时间复杂度为O（n）。

平均情况：

综合两种情况，直接插入排序的时间复杂度为O（ ）。

2.空间复杂度

算法中除了用于标记的临时变量外，没有借助额外的辅助空间，所以空间复杂度为O（1）。

3.稳定性

因为直接插入排序是按顺序依次拿取元素进行插入的，且碰到相同元素时，默认是插入到相同元素的后面，没有改变相同元素的相对次序，所以直接插入排序是稳定的。