0%

算法基础——插入排序与归并排序

这篇文章主要是依照《算法导论》这本书来写的,期间边看书边看MIT的公开课 ,课是本书的作者之一讲的,这篇文章我会着重讲讲我听不明白的一些问题,并一一解决,文章篇幅较长,希望能耐心看完哦。

简单的介绍

回忆起第一次接触排序问题,是在大一的C语言课上,老师要我们通过两个for循环把一个数组中的元素从小到大排序,看着网上的技术博客勉勉强强写出来后,才知道这叫做冒泡排序,再后来,学了把两个有序的数组合并成一个大的有序数组,也就是这次归并排序的雏形。学习Java后,遇到排序问题,一般直接调用sort函数。仔细想想,其实我们排序数组的方法有那么多种,怎么写代码去实现的方法就更多了,那种好一些,那种坏一些,我从来没有仔细探究过,但在《算法导论》中,作者并没有强调源码怎么写,而是探究更深层次的问题,代码的性能优劣。

什么是性能

性能就是程序的运行速度,但是,一个程序的优劣,不仅仅要看性能,还要看许多其他的方面,比如安全性,可维护性。

打个比方吧,假如你是一名学霸,每次考数学的时候,你都能提前半个小时把卷子写完,然后潇洒地提前交卷,但是,你总是跟全班第一差10分,你很苦恼,去问数学老师,老师说,你下次写慢点,不确定的题多检查一下,把字迹写工整一些。果然,下一次考试,你虽然没有像以往一样提前交卷,但你成了全班第一。

通过这个比方,我们可以知道,把卷子写的飞快,但是无法保证正确不行,字迹不工整不行。回到代码,一个程序,一秒钟就执行完了,但是结果是错的,另一个程序,一分钟才执行完,但是保证百分百正确。同样的例子还有很多,性能嘛,跟正确性,安全性等等没法比。**但是就像MIT的公开课里说的,性能就像货币,人要的不是更多的钱,而是钱能买来的东西。**尽管同样的程序,Java写的比C要慢很多,但是我们愿意用Java写程序,因为它能实现更多的功能。性能总是作为牺牲,去满足别的需求,这就是性能为什么处于底层的原因。

让我们通过一个都遇到过的例子来再说明一下吧。学习C语言时,都学多scanf函数吧,当我们兴奋的把写好的程序给同学运行时,同学往往不知道要输入啥,这时,我们需要用printf(“请输入一个XX数:”),来提示同学要输入什么内容,加上这一段代码,程序就变得*“冗余”*了一些,多运行了一段代码,稍微慢了一些,但是,加强了我们代码的可读性。

说了这么多,相信大家都明白了性能的含义和作用,那么让我们来看看第一个算法——插入排序吧!

插入排序

插入排序的伪代码

1
2
3
4
5
6
7
for j = 2 to A.length   //从第二个数遍历到数组末尾,j代表要比较的数
key = A[j] //记录A[j]的初始值
i = j - 1 //i代表j的后一个数
while i > 0 and A[i] > key
A[i + 1] = A[i]
i = i - 1
A[i + 1] = key //把A[j]的初始值赋给最后i前面的一个数

先讲一下伪代码,主要有两个作用,用最简的语言表示算法,让无论学过什么语言的人都能最快看懂。最简不用多说,没分号,没大括号,循环用缩进表示,颇有python内味,我在原书代码的基础上加了一些注释,相信要看懂更加容易了。如果实在看不懂伪代码,可以看这篇博客,里面用各种语言写了插入排序。

我曾经做了一个作死的尝试,写了篇名叫不用代码讲插入排序的文章,后来写的冗长不说,意思也表达不清,索性作罢,用伪代码讲算法,虽然抽象,但是精确,简洁。

让我们用一串数组,来描述这个代码的执行过程

{1, 2, 3, 5, 4}

要把这个数组变成{1, 2, 3, 4, 5}会经历什么过程呢?

1, 2, 3, 5, 5 第一步

1, 2, 3, 4, 5 第二步

我们可以看到,其实,伪代码主要实现两种功能

前提

在上面的例子中,要排序4这个数,前提是4前面的数必须有序,因为排序是从2个数到3个数到4个数……排序3个数的基础是前面的2个数已经排好了,所以不要用类似{2,1,3,5,4}这样的不标准数组来测试代码哦,同时伪代码的数组并非从0开始,而是从1开始,A[5]的元素有A[1,2,3,4,5]而不是A[0,1,2,3,4]。

移动

1
2
3
while i > 0 and A[i] > key
A[i + 1] = A[i]
i = i - 1

先看while中后面的那一部分,A[i] > key,配合后面的i = i - 1,从j的后面一个数开始,从后往前跟A[j]比大小

i > 0是为了确定数组是否到头的,如果i自减到0,while循环就会停止

看前面的文章可以知道,key就是要插入的那个值,假设数组中的第五个数也就是A[5]的值是key,A[4],A[3],都比key大,A[2]比key小,如数组{1,2,4,5,3},那么请拿出一张草稿纸,试着执行一下循环里面的代码。执行完循环之后,会得到这样一个数组{1,2,2,4,5},i最后自减完的值是2,如果细心的话,会发现数组中元素的位置已经移动了,比3大的4和5,已经从原来的位置往后移动了一位,这时,只需要把第3个位置的2换成3,数组的排序就完成了。

插入

实现插入的代码只有一行

1
A[i + 1] = key 

再用{1,2,4,5,3}举例子,我们进行完移动的操作后,得到的成果有{1,2,2,4,5}以及一个i值,i = 2

这里的i为插入操作进行引导,执行完A[i] > key和i的自减后,我们可以知道,i前面的值都比key值小,A[i] = A[i + 1],只需要把A[i + 1]替换为原来的A[j]值,即key,排序就完成了,看似是插入,如果执行过一遍程序后,就知道其实应该叫做替换。

代码运算时间分析

该从哪个角度分析?

运算时间受到的影响太多了,同样的代码,在超算和个人电脑上,运算时间肯定不同,个人电脑中,处理器型号,内存大小,也会导致执行的速度也不一样,但是,现在,我们仅从代码写法的角度来讨论运算时间的问题,而且是在最差的情况下的时间。

为什么是最差的情况

任何一个程序需要尽可能考虑差的情况,比如,一个排序数组的程序,在别人运行的时候,事先说明,本程序排序完全颠倒的数组会很慢(类似{5,4,3,2,1}),其他时候都挺快的,我觉得挺可笑的。一个程序设计的初衷就是要满足客户的各种合理需求的。记得在高考填志愿的时候,我不止一次抱怨填报志愿的网站做的差,好歹是全国人都会用的系统,为什么这么的“简朴”,后来经历过英语六级报名日语n2报名后,发现其实做的网站都这样。后来仔细一想,其实全国的电脑中很大一部分是事业单位,高中机房中的老式电脑,不仅装的是XP系统,还装有360系,毒霸系的流氓软件,要是网页做的跟苹果官网一样,一些电脑真不一定打得开。这些官方报名网站,设计时就考虑了兼容性的情况,同样,我们的代码也要考虑最差的情况。

再看一次伪代码

1
2
3
4
5
6
7
for j = 2 to A.length                a1 
key = A[j] a2
i = j - 1 a3
while i > 0 and A[i] > key a4
A[i + 1] = A[i] a5
i = i - 1 a6
A[i + 1] = key a7

a1,a2……a7对应的每一行代码的执行时间

在输入后,我们规定运算总时间是T,T的值应该为
T =n1a1 + n2a2 + ……n7a7

根据前面,算法要考虑最坏的情况,所以,我们默认排序的数组都是像{5,4,3,2,1}这种完全相反的数组,我们就可以得到n元素数组排序的最长时间。

1
2
3
4
5
6
7
for j = 2 to A.length                  a1		n
key = A[j] a2 n - 1
i = j - 1 a3 n - 1
while i > 0 and A[i] > key a4 2 + …… + n
A[i + 1] = A[i] a5 1 + …… + n - 1
i = i - 1 a6 1 + …… + n - 1
A[i + 1] = key a7 n - 1

后面的数代表执行次数,下面我来逐行讲解
1 从2到n的遍历,看似应该执行n - 1次,但是循环的条件句最后还要判断一下,所以加一,如果这里不明白,可以看第4行代码的讲解
2 每对应一个j值,都执行一次,共有n - 1个j值,执行你n - 1次
3 与第2行一样
4 由于是最差的情况,所以i每次都会自减到0,当i自减到0后,虽然循环内的代码不用执行,但是,是不是大于0还得比较一下,所以第4行代码是j为几就执行几次
5 相比于第4行代码,每个j值都少一次i的值的判断,所以每轮执行次数都为j - 1,所以为从1到n - 1的和
6 与第5行相同
7 与第2行相同

-------------本文结束感谢您的阅读-------------