插入排序

选择排序的复杂度是O(n^2)级别，但是对近乎有序数组能达到O(n)级别

function insertSort(arr) {
  // 第0个元素位置不用处理，从第1个元素开始
  for (let i = 1; i < arr.length; i++) {
    // 判断当前元素和前一个元素是否需要交换位置
    for (let j = i; j > 0 && arr[j] < arr[j - 1]; j--) {
      let mid = arr[j];
      arr[j] = arr[j - 1];
      arr[j - 1] = mid;
    }
  }
  return arr;
}

// 改进 通过赋值来取代交换的过程
function insertSortBetter(arr) {
  for (let i = 1; i < arr.length; i++) {
    // 保存当前元素的副本
    let curi = arr[i];
    let j = i;
    // 如果前一个元素比当前元素要大，则将前一个元素赋值给当前元素
    for (j; j > 0 && arr[j - 1] > curi; j--) {
      arr[j] = arr[j - 1];
    }
    // 循环结束时j的位置之前没有比当前元素更小的了，所以j就是当前元素应该在的位置
    arr[j] = curi;
  }
  return arr;
}

// 对一部分数据进行排序
function insertSortRange(arr, l, r) {
  for (let i = l + 1; i <= r; i++) {
    let curi = arr[i];
    let j = i;
    for (j; j > 0 && arr[j - 1] > curi; j--) {
      arr[j] = arr[j - 1];
    }
    arr[j] = curi;
  }
  return arr;
}