插入排序算法

从上图中我们可以看到，假设第一个是排好的顺序，将第二个跟前一个比较，小的话交换位置，然后再次跟前一个比较，小的话再次往前交换，直到相应的位置；内层循环，每次循环就是外层循环的个数；而内层循环则是j和j-1的比较。

综上所述有如下：

• 双层for循环
  • 外层：从i=1到最后（假设第一个是排好的顺序）
  • 内层：j = 当前遍历的，也就是i，然后比较j 和j-1，小的放前面

则有如下代码

function swap(arr, i, j){
    let temp = arr[i];
    arr[i] = arr[j];
    arr[j] = temp;
}
//sort为true时是升序，否则为降序
function insertSort(arr,sort){
  let len = arr.length;
  for(let i = 1;i< len;i++){
      for(let j = i;j>0;j--){
          let result = (sort ?  arr[j] < arr[j-1] : arr[j] > arr[j-1]);
          if(result){
              swap(arr,j-1,j);
          }
      }
  }
  return arr;
}
console.log(insertSort([4,3,5,8,1],true));

从上述，我们可以知道时间复杂度在O(n)~O(n^2)之间（即有序[1, 3, 4, 5, 8]和逆序[8, 5, 4, 3, 1]）