经典算法巡礼(三) -- 排序之插入排序
原创经典算法巡礼(三) -- 排序之插入排序
原创
jiezhu
修改于 2018-09-17 11:54:56
修改于 2018-09-17 11:54:56
插入排序，与之前的冒泡排序和选择排序一样，其名称就说明了她的原理。所谓插入排序，就是对于数组中未排序的元素，依次遍历寻找合适的位置并插入到已排序的子数组中。当数组中没有未排序的元素时，插入排序即完成。
同样，还是先展示golang实现的版本：
// Sort方法从数组头开始，将未排序的元素依次选择合适的位置插入已排序的子数组中
// 这里并不是找到合适位置后再将元素插入，而是交换元素至合适位置
// Sort中参数类型Comparable为统一的可比较接口，若为整数数组排序，则Comparable为int即可
// Sort中参数类型Compare为配合Comparable接口的比较方法，若为整数数组排序，则Compare即满足a int < a int即可
func (this *InsertionSort) Sort(a []Comparable, compare Compare) {
for i := 1; i < len(a); i++ {
for j := i; j > 0 && this.less(a[j], a[j-1], compare); j-- {
this.exch(a, j, j-1)
}
}
}要还是与之前一样，我们以数组元素的比较作为一次操作，分析插入排序其效率如何。事实上，在最差情况下，采用插入排序需要的比较次数为0+1+2+...+N-1次，简化后即为(N-1)/2*N = (N^2-N)/2 ~ N^2。而在最好的情况下，排入排序需要的比较次数则为N-1次。
可见，插入排序的时间复杂度是O(N^2)，同样是万恶的平方级别。但是，与冒泡排序和选择排序不同，插入排序所需的比较次数是与输入数组相关的，在最差的情况下才需要N^2次的操作。然而事实就是事实，插入排序还是只适用于小型数组的排序，不能满足大量数据的排序。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
评论
登录后参与评论
推荐阅读