为什么算法容易忘记之插入排序

在学习常用的排序算法时,常有这样的感觉,一看就懂,过眼就忘。原因在于没有将排序的基本思想与代码中各个循环控制变量的意义联系起来进行理解记忆。

插入排序

首先,我们要建立这样一个观念,排序无非就是有N个元素无序地放在N个位置上,排序的目的就是使这N个元素按一定的顺序放置在这N个位置上。基本的思路有两个,第一是给每个位置找到合适的元素并将该元素放置到该位置上,N个位置都放置好正确的元素后,排序完成。第二是给每个元素找到正确的位置并将该元素放置到该位置上,N个元素都找到属于自己的位置时,排序完成。这对理解各种排序算法中的循环控制变量的意义很有帮助。插入排序属于第二种。

基本思想

逐个元素给它们安排位置,只是安排位置的方式比较特别。首先,第一个位置上的元素就放在第一个位置上不动。第2个位置上的元素和它前面位置上的第1个元素比较,根据比较结果,调整第2个元素的位置,使前两个位置上的元素是有序的。第3个位置上的元素与前两个位置上的元素比较,根据比较结果调整第3个元素的位置,使前三个位置上的元素是有序的,然后依次是第4,5,6...个位置上的元素,一直到第N个位置上的元素找到自己的位置时,N个位置上的元素已经“各得其所”,排序完成。

从思想到代码

根据上述思想,我们首先给所有的位置从0到N-1编号。下面我们一步一步分析,按照上面的思想我们需要哪些变量,首先我们需要一个循环控制变量指示要调整位置的元素所在的位置,由于第一个元素不用调整,所以该变量应从1到N-1,将其命名为indexOfElmentToInsert。

然后我们需要一个变量暂存该元素的值,因为待会可能将别的元素安排到它目前所在的位置,这样可以防止丢失它的值,命名该变量为valueOfElementToInsert(简称insert),然后我们还需要一个循环控制变量用来指示insert元素应当放置的位置的序号,当然,这需要进行一定的比较后才能最终确定,根据上面的思想,该变量的值应该是在indexOfElmentToInsert-1到0之间,命名该变量为indexOfElementToCompare,该位置上的元素命名为valueOfElementToCompare(简称compare),比较的方法是如果compare比insert大,那就将valueOfElementToCompare挪到它下一个位置上,然后将indexOfElementToCompare往前挪一下(也就是减1),同时相应调整valueOfElementToCompare的值。

如果compare小于insert,说明再往前的所有元素都将小于insert,因此insert应当放置在indexOfElementToCompare+1的位置上,而该位置上的元素已经被往后挪了,我们可以放心地将insert放在这里。到此完成了一个元素的位置查找过程。所有元素都进行完一个这样的过程后,排序结束。

为什么不直接上代码

通过以上的叙述,主要是想让大家都能明白代码中的那些变量是用来做什么的,为什么需要这些变量。明白后,我们再看代码中的这些变量,就可以从感性上升到理性,自然也就很容易理解这些变量的边界值,因为排序的思想就隐含在这些变量之中。

代码在此

`insertion-sort(A)
//A代表待排序的数组
for indexOfElmentToInsert=1 to N-1
{
indexOfElmentToCompare = indexOfElmentToInsert - 1;
while(indexOfElmentToCompare>=0 && valueOfElmentToCompare>valueOfElmentToInsert)
{
A[indexOfElmentToCompare+1] = valueOfElmentToCompare;
indexOfElmentToCompare--;
}
A[indexOfElmentToCompare+1] = valueOfElmentToInsert;
}`

注:希尔排序实质上是一种分组插入排序算法,它需要一个变量叫gap,其值范围一般为[N/2]到1,感兴趣的可以查找资料,按本文的思路进行理解记忆。

原文发布于微信公众号 - 人工智能LeadAI(atleadai)

原文发表时间:2018-02-19

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

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

JavaScript之闭包问题以及立即执行函数

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

1012
来自专栏顶级程序员

Python 中的作用域规则和闭包简析

在对Python中的闭包进行简单分析之前,我们先了解一下Python中的作用域规则。关于Python中作用域的详细知识,有很多的博文都进行了介绍。这里我们先从...

3244
来自专栏GreenLeaves

JavaScript引用类型之Array类型一

一、简介 除了Object之外,Array类型恐怕是ECMAScript中最常用的类型了。下面就来分析ECMAScript中的数组与其他语言中的数组的异同性: ...

19010
来自专栏后端技术探索

分表查询统计的一个具体案例

问题描述 mysql数据库在数据量较大的情况下,对数据表进行水平分表,按照年份,如下:

451
来自专栏林冠宏的技术文章

由 System.arraycopy 引发的巩固:对象引用 与 对象 的区别

首先明确一点,System.arraycopy 操作的是数组,效果是深复制。 是不是觉得怎么和你印象的中不一样? 重点来了,对于对象数组,例如: User[]...

994
来自专栏沈唁志

PHP中系统函数http_build_query系统函数使用方法

1434
来自专栏用户2442861的专栏

python 中迭代多个序列

http://blog.csdn.net/he_jian1/article/details/40819407

332
来自专栏林冠宏的技术文章

由 System.arraycopy 引发的巩固:对象引用 与 对象 的区别

作者:林冠宏 / 指尖下的幽灵 腾讯云+社区:https://cloud.tencent.com/developer/user/1148436/acti...

1979
来自专栏Golang语言社区

Go语言基本的语法和内置数据类型初探

Go令牌 Go程序包括各种令牌和令牌可以是一个关键字,一个标识符,常量,字符串文字或符号。例如,下面的Go语句由六个令牌: fmt.Println("Hell...

2625
来自专栏互联网杂技

Javascript获取数组中的最大值和最小值的方法汇总

比较数组中数值的大小是比较常见的操作,下面同本文给大家分享四种放哪广发获取数组中最大值和最小值,对此感兴趣的朋友一起学习吧 比较数组中数值的大小是比较常见的操作...

2575

扫码关注云+社区