经典算法巡礼(三) -- 排序之插入排序

插入排序,与之前的冒泡排序选择排序一样,其名称就说明了她的原理。所谓插入排序,就是对于数组中未排序的元素,依次遍历寻找合适的位置并插入到已排序的子数组中。当数组中没有未排序的元素时,插入排序即完成。

同样,还是先展示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次的操作。然而事实就是事实,插入排序还是只适用于小型数组的排序,不能满足大量数据的排序

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

编辑于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏java工会

Java基础第二阶段知识点,招初级java的面试官都在问这些

JDK:是java开发的工具箱,包含jre,还包含将java文件编译为class文件的javac工具类(编译器),除此之外还包括java原生的API;包含J2S...

1251
来自专栏专注数据中心高性能网络技术研发

[Effective Modern C++(11&14)]Chapter 3: Moving to Modern C++

2286
来自专栏mathor

异常的捕获与处理

1712
来自专栏菩提树下的杨过

温故而知新:new与override的差异以及virtual方法与abstract方法的区别

先直接看代码吧: using System; namespace ConsoleApplication1 { class Program { ...

1988
来自专栏猿人谷

《C++ primer》--第1,2章小结

 1、变量初始化:  定义变量时,应该给变量赋初始值,除非确定将变量用于其他意图之前会覆盖这个初值。如果不能保证读取变量之前重置变量,就应该初始化变量。变量...

21610
来自专栏机器学习从入门到成神

一道归并排序题的解析

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/sinat_35512245/articl...

812
来自专栏AI研习社

最常见的 35 个 Python 面试题及答案(2018 版)

作为一个 Python 新手,你必须熟悉基础知识。在本文中我们将讨论一些 Python 面试的基础问题和高级问题以及答案,以帮助你完成面试。包括 Python ...

6733
来自专栏java工会

Java基础第二阶段知识点,招初级java的面试官都在问这些

1554
来自专栏微信公众号:Java团长

深入理解Java:String

按照官方的说法:Java 虚拟机具有一个堆,堆是运行时数据区域,所有类实例和数组的内存均从此处分配。

1051
来自专栏coding for love

JS原生引用类型解析7-Promise类型

ES6引入了一个全新的对象Promise,用于表示一个异步操作的最终状态(完成或失败),以及其返回的值。Promise最直接的好处就是链式调用,另外在错误捕获上...

701

扫码关注云+社区

领取腾讯云代金券