2016-11-02

算法学习:插入排序

缘起

最近打算好好学习算法。因为专业的原因,对计算机原理、数据结构与算法这些知识,一开始可以说是一窍不通的。

最开始在项目中接触算法,完全基于项目需要。当时负责一个酒店项目,数据接入来自公共部分。项目详情页拿到的数据,包括当前酒店所有套餐,最多的可能有几十个。需求仅仅要求显示三条,而且结果是根据不同内容(如状态、网络、热水、空调等等)有优先级的。

当时被这套逻辑闹得很揪心。后来想想,放手干吧,多做几次遍历。最后在排序这块遇到问题了。结果就是在阮大神的博客上找到了一个快速排序的例子,稍作修改,就用在项目中了。当时还觉得小有成就。当然,后来项目经过满满一周测试,即将上线时,被取消了。

回首算来,在上一家公司一年多的时间中,我所做的项目,真正上线的真没几个。唯一上线的可能只有一个 React Native 开发的 APP,一直活到现在。当然,也有好处,学到了很多东西。

哦,对了,第一次接触算法应该是在找工作的时候。当时跑到杭州去面试,公司不大,相对传统,主营业务说白了就是 POS 机。面试我们的是软件出身的总经理,要求很简单,每人一台机器,题目相同,不管面的是 Java 还是 C++ 或者前端。一个和图有关的题目,记得后来在哪本书上看过类似的题,很经典的算法。当时,主要学习视觉、交互为主的我,完全是一脸懵的状态。结果自然不用多说。奇怪的是,第二天回到武汉,我竟然解决了,还是拿高中数学知识解决的。造化弄人,塞翁失马,焉知非福?

面试完了之后,开始读《数据结构与算法 JavaScript 描述》一书。但这本书在数据结构方面用了很大的篇幅。了解稍微多了一点,但解决问题的能力依然有限。所以这次,我打算读《算法导论》。不打算用学院派的方式学习,只求了解算法的思想,然后自己跟着试验一遍,加强了解。

好了,前言说够了。步入正题。

插入排序

想象现在你手上有十张扑克牌(假定它们在 2-10 之间),没有经过整理,顺序打乱,我们用一个数组记录如下:

下面,我们要通过一种办法对手上的牌进行排序。

首先,拿出最左侧的一张牌 cardA,放在桌面上:

接着进行第二次取牌,依然拿手上最左侧的第一张 cardB,然后将这张牌与桌面上的牌 cardA 进行比较。

在我们的例子中,因为 cardB(3) 小于 cardA(7),所以将 cardB(3) 放在 cardA(7) 的左侧:

第三步,拿出手上左侧第一张 cardC,将它和桌面上的两张牌进行比较。这时候,因为 cardB(3) < cardC(5) < cardA(7),所以我们将这次从手上拿出的牌插入到桌面两张牌之间。

我们继续上面的步骤。从前面的步骤可以看出,每次从手上拿出一张牌之前,桌面的牌是已经排好序的。我们只需要将此次拿出的牌与桌面上的牌一一比较,找到合适的位置插入即可 —— 记住,插入位置后面所有牌的位置都相应加 1,这点很重要。

这样一来,我们就有了下面这个纯粹是 JavaScript 思维式的代码:

OK,一个 JavaScript 版本的插入排序就这样实现啦!

不过,聪明如你,肯定会去搜索一番,怎么和其他的不一样啊?没关系,我们来继续改进。

在上面的算法实现中,我们预设了一个 sorted 数组,相当于我们桌面的牌。我相信,聪明如你,牌技肯定不差,要照这么一张张往桌子上放,多累!我们整理手上的牌时,一般都是在一只手上完成的好吗?

该怎么实现呢?我们直接看代码,相信有了上面的分析,很容易就能看懂。

最近刚刚给博客新增了复制代码的功能(PC 下方可见)。可以直接复制前面的代码,测试一下~

简单分析插入排序的时间复杂度。考虑两个极端情况。

最好的情况是给定的数组已经排序好的,每次拿到的数向左对比一次就可。对比一次后,while 循环根本就不会进入。所以 for 循环中每次只需要一次对比,算起来最后就是 (n - 1) 次循环。

最差的情况是数组是完全逆序的,每次拿到的数必须一直向前进行对比,直到最左侧的数字为止。考虑第 i 个数,需要与前面对比 (i - 1) 次,累计起来总次数就是 次。

取最好情况与最差情况的平均数:

经过上面粗略的估算,可以得出插入排序的时间复杂度为 O(n^2)。