如何实现插入排序以及进行单元格测试

插入 排序 之所以叫插入排序，你可以这样理解：

假设你在打 扑克牌

通常我们需要将牌排好序，那么这个时候你是怎样排序的呢？

首先 我们手里一张牌都没有。

然后 我们拿到 第一张 牌这时候他不需要排序，也就是说它是 有序的 。

所以我们可以得到如下代码。

function insertionSort(arr) {
  // 第一张牌是有序的直接放入数组
  const result = [arr[0]];
  return result;
}
复制代码

紧接着我们拿到了第二张牌，这张牌可能比手里原有的牌大，也可能小，也可能相等只是花色不一样。

这时不论大小与否，你都要确定你想怎么排列它，我的意思是你要在升降序这两个选项里做一个抉择。

假设你选择了升序：

（注意：虽然手里只有一张牌但是，还是需要遍历整个牌组。）

那么如果这张牌比第一张大，你会接着比较这张牌是否比第二张牌大，直到你找出这张牌 比前一张牌大但是比后一张牌小 的位置，将它 插入 . （总结起来就是只要这张牌比与他比较的牌小就插入在这张牌之前，否则接着比较）

降序则是 比前一张牌小但是比后一张牌大 。

这时我们得到

function insertionSort(arr) {
  // 第一张牌是有序的直接放入数组
  const result = [arr[0]];
  const { length } = arr;
  // 这层循环是模拟发除第一张牌以外剩下的牌
  for (let i = 1; i < length; i++) {
    const original = result.length;
    // 这层循环是将新发下来的牌与手里的每一张牌比较看看它比哪张大，比哪张小。
    for (let j = 0; j < original; j++) {
      // 只要这张牌比与他比较的牌小
      if (result[j] > arr[i]) {
        // 就插入在这张牌之前
        result.splice(j, 0, arr[i]);
        // 插入之后结束本轮比较
        break;
      }
      // 否则接着比较
    }
    // 比所有的都大
  }
  return result;
}
复制代码

其中有两个特殊情况

1、 这张牌是最小的

最小的牌直接在最前面插入
复制代码

这种情况前面的代码已经包括了直接插入

2、 这张牌是最大的

最大的牌直接在最后面插入
复制代码

这种情况的代码如下:

function insertionSort(arr) {
  // 第一张牌是有序的直接放入数组
  const result = [arr[0]];
  const { length } = arr;
  // 这层循环是模拟发除第一张牌以外剩下的牌
  for (let i = 1; i < length; i++) {
    const oldLen = result.length;
    // 这层循环是将新发下来的牌与手里的每一张牌比较看看它比哪张大，比哪张小。
    for (let j = 0; j < oldLen; j++) {
      // 只要这张牌比与他比较的牌小
      if (result[j] > arr[i]) {
        // 就插入在这张牌之前
        result.splice(j, 0, arr[i]);
        // 插入之后结束本轮比较
        break;
      }
      // 否则接着比较
    }
    // 比所有的都大说明没有插入手牌说明手里的牌没有增多
    if (oldLen === result.length) {
      result.push(arr[i]);
    }
  }
  return result;
}
复制代码

至此排序过程完成需要测试一下。

如何使用 mocha 测试 排序算法

mocha 是做单元格测试的 npm 包之一。还有其他的，就不介绍了。

1、首先需要下载 mocha

yarn global add mocha
复制代码

或者：

sudo npm i mocha -g
复制代码

2、新建 test.js 文件 或者新建 test/test.js 也行看个人喜好。

3、官网有一个例子

var assert = require('assert'); // 引入测试包
describe('Array', function() { // 描述 数组
  describe('#indexOf()', function() { // 的 indexOf 函数
    // 在找不到对应元素的情况下应该返回 -1
    it('should return -1 when the value is not present', function() {
      assert.equal([1, 2, 3].indexOf(4), -1); // 第一个人参数是要测试的函数 ，  第二个参数是结果 。
    });
  });
});
复制代码

结果：

测试一个 排序算法 是否正确我准备了 4 个例子 （被测试数据 => 期望结果）

1、正整数

[1,3,2] => [1,2,3]
复制代码

describe('insertionSort([1,3,2])',function(){ // 描述 函数排序 [1,3,2]
    it('should return [1,2,3]',function(){ // 应该返回 [1,2,3]
        assert.equal( JSON.stringify(insertionSort([1,3,2])), JSON.stringify([1,2,3]) ) // 第一个参数的返回值应该等于第二个参数
    })
})
复制代码

2、负数

[-1,-3,-2] => [-3,-2,-1]
复制代码

describe('insertionSort([-1,-3,-2])',function(){
    it('should return [-3,-2,-1]',function(){
        assert.equal( JSON.stringify(insertionSort([-1,-3,-2])), JSON.stringify([-3,-2,-1]) )
    })
})
复制代码

3、小数

[0.1,-0.1,0] => [-0.1,0,0.1]
复制代码

describe('insertionSort([0.1,-0.1,0])',function(){
    it('should return [-0.1,0,0.1]',function(){
        assert.equal( JSON.stringify(insertionSort([0.1,-0.1,0])), JSON.stringify([-0.1,0,0.1]) )
    })
})
复制代码

4、 综合

[3,2,1,11,22,33,-33,-22,-11,-3,-4,-5,3.3,1.1,1.01] 
=>
[-33, -22, -11, -5, -4, -3, 1, 1.01, 1.1, 2, 3, 3.3, 11, 22, 33]
复制代码

describe('insertionSort([3,2,1,11,22,33,-33,-22,-11,-3,-4,-5,3.3,1.1,1.01])',function(){
    it('should return [-33, -22, -11, -5, -4, -3, 1, 1.01, 1.1, 2, 3, 3.3, 11, 22, 33]',function(){
        assert.equal( JSON.stringify(insertionSort([3,2,1,11,22,33,-33,-22,-11,-3,-4,-5,3.3,1.1,1.01])), JSON.stringify([-33, -22, -11, -5, -4, -3, 1, 1.01, 1.1, 2, 3, 3.3, 11, 22, 33]) )
    })
})
复制代码

测试结果：

代码

原文链接

(完)