vlambda博客
学习文章列表

排序算法系列3-插入排序


  • 属于 比较算法 [1]
  • 英文简写:INS (instagram的简写也是ins,这很有趣)

插入排序有点类似于整理扑克牌,按照顺序插入扑克牌。

关注、评论、转发

定义

  1. 从你手中的一张牌开始,
  2. 选择下一张卡并将其插入到正确的排序顺序中,
  3. 对所有的卡重复上一步。

举个例子🌰:假设你拿到4张牌[40,13,20,8](假设牌数大小不受限)
第一次插入:[13,40,20,8], 13<40,交换位置
第二次插入:[13,20,40,8], 13<20<40,20和40交换位置
第三次插入:[8,13,20,40], 8比前面的数都小,8插入到首位

// C++
void insertionSort(int a[], int N) {
  for (int i = 1; i < N; ++i) { // O(N)
    int X = a[i]; // X 是将要插入的
    int j = i-1;
    for (; j >= 0 && a[j] > X; --j) // 可能快或慢
      a[j+1] = a[j]; // 给X标记位置
    a[j+1] = X; // j+1是插入点位置
  }
}

时间复杂度

很明显,外循环执行N-1次。但内循环执行的次数取决于输入:

  1. 在最好的情况下,数组已经排序并且(a [j]> X)总是为假所以不需要移位数据,并且内部循环运行在O(1),
  2. 在最坏的情况下,数组被反向排序并且(a [j]> X)始终为真插入始终发生在数组的前端,并且内部循环以O(N)运行。因此,最佳情况时间是O(N × 1) = O(N) ,最坏情况时间是O(N × N) = O(N^2).

综上,插入排序的时间复杂度介于O(N)~O(N^2)之间。

分析

插入排序不需要额外空间,是本地排序,相等元素不会交换前后顺序,所以是稳定排序[2],时间复杂度为O(n^2),适用于少量数据排序。

问题

前篇介绍的冒泡排序选择排序是稳定算法吗?欢迎在评论区留言讨论。

参考资料

[1]

什么是比较算法: 是指基于比较而比较,因为它们比较数组的元素并决定是否交换它们。

[2]

稳定排序: 简单来说,就是根据排序规则,原数组元素的相对位置不会改变。比如[5,5,5,5],根据插入算法不需要交换位置,所以插入算法是稳定的。