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

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

插入排序

首先,我们要建立这样一个观念,排序无非就是有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 条评论
登录 后参与评论

相关文章

来自专栏程序员互动联盟

【面试宝典】static 关键字

面试官:static关键字你了解吗?说一下你的认识。 小白:啊.....有点晕呀,这么宽泛的问题,我该从哪回答呢?头脑一片空白。让我想想...... 面试官:没...

3556
来自专栏云霄雨霁

排序----归并排序

1460
来自专栏ACM算法日常

字符串展开(递归)- HDU 1274

常用纱线的品种一般不会超过25种,分别可以用小写字母表示不同的纱线,例如:abc表示三根纱线的排列;重复可以用数字和括号表示,例如:2(abc)表示abcabc...

762
来自专栏java学习

面试题18(覆盖(重写)与重载的关系是什么?)

覆盖(重写)与重载的关系是什么? A) 覆盖(重写)只有出现在父类与子类之间,而重载可以出现在同一个类中 B)覆盖(重写)方法可以有不同的方法名,而重载方法必须...

2788
来自专栏老九学堂

一分钟掌握C语言结构体常见方法

把结构体名称去掉,这样更简洁,不过也不能定义其他同结构体变量了——至少我现在没掌握这种方法。

792
来自专栏Python

数据类型总结(二)(列表,元组,字典)

一.变量的赋值操作 x=1 a=10 b=10 # #链式赋值 a=b=c=d=e=f=10 print(a,b,c,d,e,f) #多元赋值 #方式一 x...

2928
来自专栏GreenLeaves

JavaScript之apply()和call()的区别

我 在一开始看到javascript的函数apply和call时,非常的模糊,看也看不懂,最近在网上看到一些文章对apply方法和call的一些示 例,总算是看...

2017
来自专栏java一日一条

JavaScript 函数式编程中的 curry 实现

最近在学习javascript函数式编程,对其中大名鼎鼎的curry十分感兴趣,curry函数可以接受一个函数,我们暂且称之为原始函数,返回的也是一个函数,柯里...

784
来自专栏Python小屋

Python求解进制问题(阿里巴巴2015笔试题)

问题描述:用十进制计算30的阶乘,然后把结果转换成三进制表示,那么该进制表示的结果末尾会有多少个连续0? 解析:作为笔试题的话,要想按照题意先把阶乘结果计算出来...

3387
来自专栏小古哥的博客园

秒懂JS对象、构造器函数和原型对象之间的关系

学习JS的过程中,想要掌握面向对象的程序设计风格,对象模型(原型和继承)是其中的重点和难点,拜读了各类经典书籍和各位前辈的技术文章,感觉都太过高深,花费了不少时...

2987

扫码关注云+社区