生活中的例子，在打扑克牌的时候，人们是如何进行扑克牌排序的呢？比如我手中有6，7，9，10这四张牌，已经处于升序

这个时候，又抓到了一张 8，如何让手中的五张牌重新变成升序的呢？用冒泡排序？选择排序？或者快速排序？

恐怕正常打牌的人都不会这么做，最自然也是最简单的方式，是在已经有序的四张牌中找到 8 应该插入的位置，也就是 7 和 9 之间，把红桃 8 插入进去

就像玩牌一样，插入排序也是类似的思想：维护一个有序区，把元素一个一个插入到有序区的适当位置，直到所有元素有序

初识插入排序

给定无序数组

把数组的首元素 5，作为有序区，此时有序区只有这一个元素

第一轮：

让元素 8 和有序区依次比较，8 > 5，所有元素 8 和元素 5 无需交换，此时有序区的元素增加到两个

第二轮：

让元素 6 和有序区依次比较， 6 < 8，所以元素 6 和元素 8 进行交换

6 > 5，所以元素 6 和元素 5 无需交换，此时，有序区元素增加到 3 个

第三轮：

让元素 3 和有序区依次比较，3 < 8 所以元素 3 和元素 8 交换位置，

3 < 6，所以元素 3 和元素 6 交换位置

3 < 5，所以元素 3 和元素 5 交换位置

此时，有序区元素增加到 4 个

依次类推，插入排序一共会进行 数组的长度 - 1 轮，每一轮结果如下

优化

当把每一个新元素插入到有序区时，并不需要老老实实的进行两两交换

以第三轮举例：

原本的做法是，让让元素 3 逐个与有序区的元素进行比较和交换，和 8 交换，和 6 交换，和 5 交换，最终交换到一个有序的位置

但是其实并不需要真正的交换，只需要把元素 3 暂存起来，再把有序区的元素，从左向右逐一复制

第一步，暂存元素 3

第二步，和前一个元素比较，由于 3 < 8，复制元素 8 到它的下一个位置

第三步，和前一个元素比较，由于 3 < 6，复制元素 6 到它的下一个位置

第四步，和前一个元素比较，由于 3 < 5，复制元素 5 到它的下一个位置

第五步，也就是最后一步，把元素 3 赋值到数组首位

这样的优化方法减少了许多无谓的交换

实现代码

1  function insertSort(arr:Array<number>) {
2  
3  
4      for (let index = 1; index < arr.length; index++) {
5          let temp = arr[index];
6          let j = index - 1;
7          // 从右比较元素 并且右移
8          for (; j >= 0 &amp;&amp; arr[j] > temp; j--) {
9              arr[j + 1] = arr[j]            
10          }
11          // 插入insertValue
12          arr[j + 1] = temp        
13      }
14  
15  
16      return arr
17  };
18  
19  
20  function main() {
21      let arr = [12, 1, 3, 46, 5, 0, -3, 12, 35, 16]
22      console.log(insertSort(arr))
23  };
24  
25  
26  main();
27

小结

时间复杂度：

插入排序要进行 n - 1 轮，每一轮在最坏的情况下要比较复制 1，2，3，4，5.... n - 1次，所以最坏时间复杂度为 O(n2)

空间复杂度

O(1)

摘要总结公众号：程序员小灰 文章