原理：

  • 将元素分为已排区间和未排区间
  • 取未排区间的元素插入到已排区间的正确位置，保证已排区间顺序正确
  1. function insertSort(arr){
  2.     const len = ar.length;
  3.   if(!len)return;
  4.   for(let i=1;i<len;i++){
  5.       const v = arr[i];
  6.     let j = i-1;
  7.     for(;j>=0;--j){
  8.         if(arr[j]>v){
  9.           arr[j+1] = arr[j];
  10.       }else{
  11.           break;
  12.       }
  13.     }
  14.     arr[j+1] = v;// v最小的情况下，将数组插入到头；在v最大的情况下，恢复原结构
  15.   }
  16. }
  • 空间复杂度O(1) 是原地排序
  • 是稳定排序
  • 最好O(n)
  • 最坏O(n)
  • 平均O(n)