03插入排序

插入排序是一种最简单直观的排序算法，它的工作原理是通过构建有序序列，对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。

插入排序步骤：

1. 将序列第一个元素看做一个有序序列，把第二个元素到最后一个元素当成是未排序序列。
2. 从头到尾依次扫描未排序序列，将扫描到的每个元素插入有序序列的适当位置。（如果待插入的元素与有序序列中的某个元素相等，则将待插入元素插入到相等元素的后面。）

以下面5个无序的数据为例：
65 27 59 64 58 （文中仅细化了第四次插入过程）

• 第1次插入: 27 65 59 64 58
• 第2次插入: 27 59 65 64 58
• 第3次插入: 27 59 64 65 58
• 第4次插入: 27 58 59 64 65

let arr = [65, 27, 59, 64, 58];

function insertSort(arr) {
  for (let i = 1; i < arr.length; i++) { // 从第2个元素开始插入
    console.log('排序前：'+arr);
    let temp = arr[i];　// 待插入元素
    j = i - 1;
    while (j >= 0 && temp < arr[j]) { // 从后向前，找到比其小的数的位置
        arr[j + 1] = arr[j]; // 向后移动
        console.log('排序中!!调整：'+arr);
        j--;
    }
    console.log('需在位置'+(j+1)+'插入元素.....'+temp)
    arr[j + 1] = temp;
    console.log('排序后：'+arr);
    console.log('-------------------');
  }
  console.log('最终结果:'+arr);
  return arr;
}

insertSort(arr);

最佳情况：输入数组按升序排列。T(n) = O(n) 最坏情况：输入数组按降序排列。T(n) = O(n2) 平均情况：T(n) = O(n2)
上述属于直接插入排序
还可以有折半插入排序和希尔排序

排序前：65,27,59,64,58
排序中!!调整：65,65,59,64,58
需在位置0插入元素.....27
排序后：27,65,59,64,58
-------------------
排序前：27,65,59,64,58
排序中!!调整：27,65,65,64,58
需在位置1插入元素.....59
排序后：27,59,65,64,58
-------------------
排序前：27,59,65,64,58
排序中!!调整：27,59,65,65,58
需在位置2插入元素.....64
排序后：27,59,64,65,58
-------------------
排序前：27,59,64,65,58
排序中!!调整：27,59,64,65,65
排序中!!调整：27,59,64,64,65
排序中!!调整：27,59,59,64,65
需在位置1插入元素.....58
排序后：27,58,59,64,65
-------------------
最终结果:27,58,59,64,65