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

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

插入排序

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

相关文章

来自专栏数据结构与算法

31:字符串p型编码

31:字符串p型编码 总时间限制: 1000ms 内存限制: 65536kB描述 给定一个完全由数字字符('0','1','2',…,'9')构成的字符串s...

4506
来自专栏九彩拼盘的叨叨叨

JavaScript 的变量和数据类型

信息是由数据组成的。变量可以理解成装数据的“盒子”。操作某个数据,首先要做是找到数据所在的盒子(变量)。放在变量里的数据称为变量值。

452
来自专栏海天一树

小朋友学经典算法(12):分割字符串

在分割字符串之前,先来了解一些跟字符串相关的变量或函数: (1)size_type:size_type由string类类型和vector类类型定义的类型,用以保...

872
来自专栏编程

python学习第二天:python的函数、循环和条件、类

第一天学习了Python的基本操作,以及几种主要的容器类型,今天学习 ,这样才算对Python有一个大致的了解。今天的学习大纲如下: 三、函数 1、定义函数 四...

1616
来自专栏简书专栏

Python闭包函数和装饰器

1.概念:在一个外函数中定义了一个内函数,内函数运用了外函数的临时变量,并且外函数的返回值是内函数的引用 示例代码:演示函数嵌套和闭包。

774
来自专栏前端架构与工程

【译】《Understanding ECMAScript6》- 第一章-基础知识(一)

目录: 更好的Unicode编码支持 codePointAt()函数 String.fromCodePoint() 用转义序列对Non-BMP字符编码 nor...

2225
来自专栏java一日一条

JavaScript 函数式编程中的 curry 实现

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

544
来自专栏数据结构与算法

1807. [NOIP2014]寻找道路P2296 寻找道路

题目描述 在有向图G 中,每条边的长度均为1 ,现给定起点和终点,请你在图中找一条从起点到终点的路径,该路径满足以下条件: 1 .路径上的所有点的出边所指向的点...

2826
来自专栏desperate633

LintCode 二进制中有多少个1题目分析

这种方法速度比较快,其运算次数与输入n的大小无关,只与n中1的个数有关。如果n的二进制表示中有k个1,那么这个方法只需要循环k次即可。其原理是不断清除n的二进制...

441
来自专栏瓜大三哥

HLS Lesson6-数据类型转换

1.整数数据类型 传统的C语言可以采用:数据类型 数据变量 赋值 int var = -1; ap_int<6> a_6bit_var_c = -22;//复制...

23710

扫描关注云+社区