实现原理
插入排序的原理是:我们将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。
如下图所示:
在这里搭配动态图查看效果更佳:https://visualgo.net/zh/sorting。
示例代码
插入排序也比较简单,实现代码如下:
void insertionSort(int a[], int N) {
for (int i = 1; i < N; ++i) { // O(N)
int X = a[i]; // X is the item to be inserted
int j = i-1;
for (; j >= 0 && a[j] > X; --j) // can be fast or slow
a[j+1] = a[j]; // make a place for X
a[j+1] = X; // index j+1 is the insertion point
}
}
性能分析
- 插入排序需要两个嵌套的循环,时间复杂度是O(n2);
- 没有额外的存储空间,是原地排序算法;
- 不涉及相等元素位置交换,是稳定的排序算法。
插入排序的时间复杂度和冒泡排序一样,也不是很理想,但是插入排序不涉及数据交换,从更细粒度来区分,性能要略优于冒泡排序。
评论区