排序算法系列3-插入排序
-
属于 比较算法 [1] -
英文简写：INS （instagram的简写也是ins，这很有趣）
插入排序有点类似于整理扑克牌，按照顺序插入扑克牌。
关注、评论、转发
定义
-
从你手中的一张牌开始， -
选择下一张卡并将其插入到正确的排序顺序中， -
对所有的卡重复上一步。
举个例子🌰：假设你拿到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次。但内循环执行的次数取决于输入：
-
在最好的情况下，数组已经排序并且（a [j]> X）总是为假所以不需要移位数据，并且内部循环运行在O（1）， -
在最坏的情况下，数组被反向排序并且（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)，适用于少量数据排序。
问题
前篇介绍的冒泡排序和选择排序是稳定算法吗？欢迎在评论区留言讨论。
参考资料
什么是比较算法: 是指基于比较而比较，因为它们比较数组的元素并决定是否交换它们。
[2]稳定排序: 简单来说，就是根据排序规则，原数组元素的相对位置不会改变。比如[5,5,5,5]，根据插入算法不需要交换位置，所以插入算法是稳定的。