剑客
关注科技互联网

算法学习:插入排序 · 文蔺的前端之路

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

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

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

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

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

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

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

插入排序

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

var cards = [7, 3, 5, 10, 6, 9, 2, 7, 9, 4];
// 生成方法如下
// var arr = [];
// var t =10;
// while (t) a[--t] = ~~(Math.random()*9) + 2

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

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

Table: cardA(7)
Cards: 3 5 10 6 9 2 7 9 4

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

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

Table: cardB(3) cardA(7)
Cards: 5 10 6 9 2 7 9 4

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

Table: cardB(3) cardC(5) cardA(7)
Cards: 10 6 9 2 7 9 4

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

// 我们将桌面上排好序的牌记为数组 sorted
// 将第 n 轮(n >=0 )拿出的牌记作 cardN
// 那么找到 cardN 插入位置的办法如下:

// 从右向左找
// 只需要找到第一个比 cardN 小的即可
// 数组下标从 0 开始
var pos = sorted.length - 1;

// 开始从右向左比较
while (pos >= 0 && sorted[pos] > cardN) {
 // 比 cardN 大的都向右挪动一位
 sorted[pos + 1] = sorted[pos];
 // 向左移动
 pos--;
}

// 上面 while 循环已经将所有比 cardN 大的数都右移一位
// 空出来的位置,自然就是 cardN 应该在的位置了
// 注意次这时 pos 已经是第一个比 cardN 小的数字的位置
// 所以需加一
sorted[pos + 1] = cardN;

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

function insertionSort(cards){
 // 为了不改变原数组,便于比较
 // 我们先复制一份
 cards = cards.slice(0);

 var cardN = null;
 var sorted = [];

 // 从最左侧取出一张 直到取完
 while (cardN = cards.shift()) {
 var pos = sorted.length - 1;
 
 while (pos >= 0 && sorted[pos] > cardN) {
 // 比 cardN 大的都向右挪动一位
 sorted[pos + 1] = sorted[pos];
 // 向左移动
 pos--;
 }
 sorted[pos + 1] = cardN;
 }

 return sorted;
}

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

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

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

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

 function insertionSort(cards){
 cards = cards.slice(0);

 var len = cards.length;
 var cardN, i, j;

 // 将左侧第一张牌先看作我们的桌面上已经排好序的 sorted 数组
 // 每次循环时 i 代表当前的要插值的那张牌
 for (i = 1; i < len; i++) {
 // 当前要移动的牌
 cardN = cards[i];

 // 倒着往前对比
 // 这是最右侧那张牌
 j = i - 1;

 // 相当于 cardN 逐一不停地与其左侧排好序的牌交换位置
 // 直到找到比 cardN 小的那张
 while (j >= 0 && cards[j] > cardN) {
 cards[j + 1] = cards[j];
 cards[j] = cardN;
 j--;
 }
 }

 return cards;
}

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

关于算法复杂度的问题,有空我再补下。

分享到:更多 ()

评论 抢沙发

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址