vlambda博客
学习文章列表

• 属于 比较算法 ^[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)，适用于少量数据排序。

问题

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

参考资料