作为一个程序员，一些基本的排序算法是必须要掌握的。以前人们总觉得算法是后端程序员去学的，前端只需要专注于网页的美观以及 JS 的基本逻辑交互就行，然而，近几年随着前端行业的发展，前端越来越注重逻辑交互，如果你还像很久之前那样只知道用 HTML + CSS 去构建网页，那就落伍了。如今，前端程序员也需要对算法有一定的了解，不说别的，多掌握点东西总是好的。今天的文章介绍的是排序算法中的插入排序。

什么是排序

维基百科中这样说明：一种能将一串数据依照特定排序方式进行排列的一种算法。生活中也有很多排序的例子：超市购物排队，学生成绩排序，班级座位排序等。排序可以分为内部排序还有外部排序。内部排序是指待排序列完全存放在内存中所进行的排序过程，适合不太大的元素序列；外部排序能够处理极大量数据的排序算法，通常需要结合外存储器（硬盘）使用。

各种排序归类
各种排序归类

什么是插入排序

插入排序的原理跟扑克牌差不多，打过扑克牌的都知道，我们拿到一副牌，会按照大小将这些牌进行排列，每拿一张牌，就将它与前面的牌进行比较，比那张牌大又比那张牌小，那么就在这个位置将其插入，然后继续拿其它的牌排列，将它们都插入到符合它们顺序的位置上，这就是插入排序的原理：每次将待排序的元素抽出来，与前面的元素进行比较，如果小于则交换位置，直到大于某个元素则排在这个元素之后，插入排序每次都需要由后向前对元素进行一一比较。

实现代码

以下是插入排序的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function insertSort(arr){
   if(Object.prototype.toString.call(arr).slice(8,-1)
     === 'Array'){
     console.time('插入排序耗时: ');
     for(var i=1;i<arr.length;i++){
       var key = arr[i];
       var j = i - 1;
       while(j>=0 && arr[j] > key){
         arr[j + 1] = arr[j];
         j--;
       }
       arr[j + 1] = key;
     }
     console.timeEnd('插入排序耗时: ');
     return arr;
   }else{
     return 'this is not an Array';
   }
}

var arr = [3,44,38,5,47,15,36,26,27,2,46,4,19,50,48];
console.log(insertSort(arr));
// 插入排序耗时: : 0.255126953125ms
// [2, 3, 4, 5, 15, 19, 26, 27, 36, 38, 44, 46, 47, 48, 50]

第一行中的Object.prototype.toString.call(arr)返回的是[object Array]，然后我们通过 JS 中的slice()方法就可以判断传入的是不是一个数组，如果不是，则返回提示文字。代码中使用了一个临时变量 key 来存储需要比较的元素，通过后一个元素不断地与前一个元素进行比较，如果大了，就赋值交换，然后坐标 j– ；最后将 key 里存储的值放到正确的位置上。

时间和空间复杂度

最好的情况：T(n) = O(n)
最坏的情况：T(n) = O(n²)
平均时间复杂度是：T(n) = O(n²)
空间复杂度为：O(1)

引用

维基百科： https://zh.wikipedia.org/wiki/
代码出处： https://blog.csdn.net/jizhen_tan/article/details/52555639