前言

虽然前端面试中很少会考到算法类的题目，但是你去大厂面试的时候就知道了，对基本算法的掌握对于从事计算机科学技术的我们来说，还是必不可少的，每天花上 10 分钟，了解一下基本算法概念以及前端的实现方式。

另外，掌握了一些基本的算法实现，对于我们日常开发来说，也是如虎添翼，能让我们的 js 业务逻辑更趋高效和流畅。

算法介绍

我们都应该玩过扑克牌了，游戏期间玩家们基本上都是一边摸牌一边理牌，会把牌面值小的牌放到左边，牌面值大的牌放到右边，以升序进行排序（当然也有喜欢降序排序的玩家）。而理牌期间，我们习惯从左往右看牌面值大小，两两比较，将牌抽出，插入到合理的位置。这里我们理牌的方法，就是「直接插入排序法」。

直接插入排序法的基本操作是将一个元素插入到已经排好序的数组中，从而得到一个新的、Unicode 值递增的数组。

算法图示：

具体实现

var insertSort = function(arr){
 var i, j, m, mCnt=0;
 var len = arr.length;

 for (i=1; i<len; i++) {
 if (arr[i] < arr[i-1]) {
 // 将更小的那个元素保存起来
 m = arr[i];
 for (j=i-1; arr[j]>m; j--) {
 // 往后挪
 arr[j+1] = arr[j];
 mCnt++;
 }
 console.log('移动了 '+mCnt+' 次');
 mCnt = 0;
 // 直接插入
 arr[j+1] = m;
 }
 }

 return arr;
};

insertSort([5,4,3,2,1]);
insertSort([3, 2, 1, 7, 8, 9, 0]);
复制代码

复杂度分析

当最好的情况，也就是传入的数组本来就是有序的，比如 [1, 2, 3, 4, 5]，那么比较次数为 5-1=4 次，由于已经是有序的了，因此没有移动的次数，时间复杂度为 O(n)。

当最坏的情况，也就是传入的数组完全是逆序的，比如 [5, 4, 3, 2, 1]，那么需要比较如下次：

而移动的次数也将达到如下次数：

综上所述，时间复杂度依旧为 O(n²)。