超市老板小M有点郁闷，前不久他用了「冒泡排序」给6个基友排了位置，很高兴的和自己之前的同事说自己知道怎么优化冒泡算法了，结果同事告诉他，“实际工程中「插入排序」用得比「冒泡排序」多一些，因为其代码更加整洁，交换操作只需要一句代码（冒泡排序需要三句），在时间细节上更优。”，但是小M听了半天也没明白「插入排序」是怎么个插入法。
看着一旁又打成一团的6个好基友，小M一拍脑袋：“实践出真知呀！”于是他决定用「插入排序」给这6个好基友重新排个序。
初始状态
- 按照「插入排序」的原理，分出「已排序区」和「未排序区」。首先默认「已排序区」仅有小包一个，「未排序区」有小锣、小威、小酥、小栗和小枣
- 从「未排序区」中取出小锣，由于小锣身高 < 小包身高，于是插入到「已排序区」最前的位置
- 从「未排序区」中取出小威，由于小威身高 > 小包身高 ，于是插入到「已排序区」最后的位置
- 从「未排序区」中取出小酥，由于小酥身高 < 小锣身高 ，于是插入到「已排序区」最前的位置
- 从「未排序区」中取出小栗，由于 小包身高 < 小栗身高 < 小威身高 ，于是插入到「已排序区」小包和小威之间
- 从「未排序区」中取出小枣，由于小包身高 < 小枣身高 < 小栗身高 ，于是插入到「已排序区」小包和小栗之间
排序过程
小M发现「插入排序」的思想的确比「冒泡排序」更为简单，关键在于每次在「已排序区」中插入元素时需要保证有序，因此其时间复杂度事实上还是和「冒泡排序」一样，都是O(n2)。那为什么「插入排序」的应用更为普遍呢，小M决定用代码来验证一下：
function insertSort (arr) {
for (let i = 0; i < arr.length; i++) {
let value = arr[i];
let j = i -1;
for (; j >= 0; j--) {
if(arr[j] > value) {
arr[j+1] = arr[j]; // 数据移动
} else {
break;
}
};
arr[j+1] = value; // 插入数据
};
return arr;
}
果不其然，在循环主体内，「插入排序」数据操作只需要一句代码，而「冒泡排序」需要三句代码，这在时间细节上使得「插入排序」要更优些。
