插入排序

插入排序是一种简单直接的排序方法，其基本思想是每次将一个待排序的记录按其关键字大小插入到前面已经排好序的子序列，直到全部记录插入完成。由插入排序的思想可以引申出三个重要的排序算法： 直接插入排序、折半插入排序和希尔排序。

直接插入排序

直接插入排序是一种最直观的也是最简单的算法。

基本思想

假设在排序过程中，待排序表 L【1…n】在每次排序过程中的某一时刻状态如下：

实现逻辑：

1. 从第一个元素开始，暂定默认第一个元素是已经排好序的
2. 取出下一个元素K，在已经排好序的元素序列中从后向前扫描
3. 如果在扫描过程中，扫到一个元素大于K,那么就将该元素 移动到下一个位置
4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置
5. 将新元素插入到该元素后
6. 重复步骤2~5

演示

代码展示

let ary = [3, 8, 1, 9, 4, 5, 6, 2, 7];
function insertSort(ary, length) {
  // 暂定第一个元素是有序的；i 从1开始
  for (let i = 1; i < length; i++) {
    let temp = ary[i];
    let j = i;
    // 在有序列表中，从后向前扫描，找到插入的位置
    while (j > 0 && ary[j - 1] > temp) {
      ary[j] = ary[j - 1];
      j--;
    }
    // 在j 的位置插入新的元素
    ary[j] = temp;
    console.log(JSON.stringify(ary));
  }
  return ary;
}
insertSort(ary, ary.length);

结果：

[3,8,1,9,4,5,6,2,7]
[1,3,8,9,4,5,6,2,7]
[1,3,8,9,4,5,6,2,7]
[1,3,4,8,9,5,6,2,7]
[1,3,4,5,8,9,6,2,7]
[1,3,4,5,6,8,9,2,7]
[1,2,3,4,5,6,8,9,7]
[1,2,3,4,5,6,7,8,9]

性能分析

时间复杂度	空间复杂度
最好情况下：O（n）;最坏情况下：O（n^2）;
平均时间复杂度：O（n^2）;	仅使用了常数个辅助单元，所以空间复杂度为O(1)

总结

1. 稳定性： 由于每次插入元素时总是从后向前线比较在移动，所以不会出现相同元素相对位置发生变化的情况，所以直接插入排序是一个稳定的排序方法。
2. 适用性：直接插入排序算法使用与顺序存储和链式存储的线性表，为链表存储时，可以从前往后查找指定元素的位置。
3. 大部分排序算法都仅适用于顺序存储的线性表