本文作者:文蔺
本文地址:http://www.wemlion.com/2016/algo-insertion-sort/
本文由 @文蔺 创作，转载请保留此声明。
所有权利保留，请勿用于商业目的。

缘起

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

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

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

回首算来，在上一家公司一年多的时间中，我所做的项目，真正上线的真没几个。唯一上线的可能只有一个 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];
      // 相当于 cardN 逐一不停地与其左侧排好序的牌交换位置
      // 直到找到比 cardN 小的那张
      // 但下面这句没必要
      // cards[j] = cardN;
      j--;
    }
    // 插入 cardN 
    cards[j + 1] = cardN;
  }

  return cards;
}

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

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

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

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

取最好情况与最差情况的平均数：((n - 1) + n * (n - 1) / 2) / 2 = (n^2 + n -2) / 2。

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

本文作者：文蔺
本文地址：http://www.wemlion.com/2016/algo-insertion-sort/
转载请注明来源