描述

<1>.从第一个元素开始，该元素可以认为已经被排序；

<2>.取出下一个元素，在已经排序的元素序列中从后向前扫描；

<3>.如果该元素（已排序）大于新元素，将该元素移到下一位置；

<4>.重复步骤3，直到找到已排序的元素小于或者等于新元素的位置；

<5>.将新元素插入到该位置后；

<6>.重复步骤2~5。

实现

  1. const insertSort = arr => {
  2.   let temp;
  3.   for (let i = 1; i < arr.length; i++) {
  4.     for (let j = i; j > 0; j--) {
  5.       if (arr[j] < arr[j-1]) {
  6.         temp = arr[j];
  7.         arr[j] = arr[j-1];
  8.         arr[j-1] = temp;
  9.       }
  10.     }
  11.   }
  12.   return arr;
  13. };

时间复杂度: O(n²)