记录前端开发学习与积累

插入排序

基本算法 笔试 2017/08/16

#步骤拆解：

插入排序的思想类似于斗地主时候一边抓牌一边插进已有牌的过程

  1. 从第一个元素开始，该元素可以认为已经被排序；
  2. 取出下一个元素，在已经排序的元素序列中从后向前扫描；
  3. 如果该元素（已排序）大于新元素，将该元素移到下一位置；
  4. 重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；
  5. 将新元素插入到该位置后；
  6. 重复步骤2-5.

简单实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
function insertionSort(arr) {
    console.time('插入排序耗时');
    for (var i = 0; i < arr.length; i++) {
        var key = arr[i];//保存i位置的数值
        for (var j = i -1; j > 0; j--) {//j用于确定已排序数组的末端，可见第一次赋值操作就将arr[i]覆盖掉了，因此之前的保留是必要的，此后的判断也应使用保留值
            if (arr[j] > key) {
                arr[j+1] = arr[j];
            }
        }
        arr[j+1] = key;//将本轮需插入的值插入到已排序数组中
    }
    console.timeEnd('插入排序耗时');
    return arr;
}

#小结：
插入排序时间复杂度为O(n)-O(n^2),空间复杂度为O(1),稳定

图解：

myBlog
avatar high起来 😝
选择排序

  1. 1. 简单实现：
  2. 2. 图解：