插入排序
实现原理
插入排序的原理是:我们将数组中的数据分为两个区间,已排序区间和未排序区间。初始已排序区间只有一个元素,就是数组的第一个元素。插入算法的核心思想是取未排序区间中的元素,在已排序区间中找到合适的插入位置将其插入,并保证已排序区间数据一直有序。重复这个过程,直到未排序区间中元素为空,算法结束。
插入排序的工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。插入排序在实现上,通常采用in-place排序(即只需用到O(1)的额外空间的排序),因而在从后向前扫描过程中,需要反复把已排序元素逐步向后挪位,为最新元素提供插入空间。
整体流程如下图所示:
动图演示
示例代码
插入排序也比较简单,对应的 Go 实现代码如下:
1 |
|
性能分析
我们来看下插入排序的性能和稳定性:
- 插入排序需要两个嵌套的循环,时间复杂度是$O(n^2)$;
- 没有额外的存储空间,是原地排序算法;
- 不涉及相等元素位置交换,是稳定的排序算法。
插入排序的时间复杂度和冒泡排序一样,也不是很理想,但是插入排序不涉及数据交换,从更细粒度来区分,性能要略优于冒泡排序。