超市风云之插入排序

超市老板小M有点郁闷，前不久他用了「冒泡排序」给6个基友排了位置，很高兴的和自己之前的同事说自己知道怎么优化冒泡算法了，结果同事告诉他，“实际工程中「插入排序」用得比「冒泡排序」多一些，因为其代码更加整洁，交换操作只需要一句代码（冒泡排序需要三句），在时间细节上更优。”，但是小M听了半天也没明白「插入排序」是怎么个插入法。

看着一旁又打成一团的6个好基友，小M一拍脑袋：“实践出真知呀！”于是他决定用「插入排序」给这6个好基友重新排个序。

1. 按照「插入排序」的原理，分出「已排序区」和「未排序区」。首先默认「已排序区」仅有小包一个，「未排序区」有小锣、小威、小酥、小栗和小枣
2. 从「未排序区」中取出小锣，由于小锣身高 < 小包身高，于是插入到「已排序区」最前的位置
3. 从「未排序区」中取出小威，由于小威身高 > 小包身高 ，于是插入到「已排序区」最后的位置
4. 从「未排序区」中取出小酥，由于小酥身高 < 小锣身高 ，于是插入到「已排序区」最前的位置
5. 从「未排序区」中取出小栗，由于 小包身高 < 小栗身高 < 小威身高 ，于是插入到「已排序区」小包和小威之间
6. 从「未排序区」中取出小枣，由于小包身高 < 小枣身高 < 小栗身高 ，于是插入到「已排序区」小包和小栗之间
   排序过程
   小M发现「插入排序」的思想的确比「冒泡排序」更为简单，关键在于每次在「已排序区」中插入元素时需要保证有序，因此其时间复杂度事实上还是和「冒泡排序」一样，都是O(n²)。那为什么「插入排序」的应用更为普遍呢，小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;
}

果不其然，在循环主体内，「插入排序」数据操作只需要一句代码，而「冒泡排序」需要三句代码，这在时间细节上使得「插入排序」要更优些。