前端-直接插入排序

1. 直接插入排序

   思想: 将L[i]插入到已经有的子序列L[1...i-1]中

   1. 保存L[i]的值
   2. 查找出L[i] 在子序列L[1...i-1]中, 应该插入的位置k
   3. 将L[1...i-1]中比L[i]到的值全部往后移动一个位置
   4. 将L[k]的位置赋值为第一步中保存的L[i]的值

2. 稳定性: 稳定

3. 时间复杂度: O(n^2)

function InsertSort(arr) {
  const len = arr.length;
  let i, j;
  for (i = 1; i < len; i++) {
    // 如果后面的元素比前面的元素大的话, 表示需要调整位置
    if (arr[i - 1] > arr[i]) {
      const temp = arr[i];
      for (j = i - 1; arr[j] > temp; j--) {
        // 将比temp大的往后移动
        arr[j + 1] = arr[j];
      }
      // 将temp放在应该的位置
      arr[j + 1] = temp;
    }
  }
}

// 看 9,1的交换
const a = [5, 2, 4, 3, 8, 6, 9, 1, 0, 7];
InsertSort(a);
console.log(a)


/*
   {4,5,1,2,6,3}
   
   {1,4,5,2,6,3}
   {1,2,4,5,6,3}
   {1,2,4,5,6,3}
   {1,2,3,4,5,6}
*/