插入排序,与之前的冒泡排序和选择排序一样,其名称就说明了她的原理。所谓插入排序,就是对于数组中未排序的元素,依次遍历寻找合适的位置并插入到已排序的子数组中。当数组中没有未排序的元素时,插入排序即完成。
同样,还是先展示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 删除。