# 插入排序

function insertSort(arr){
  for (let i = 1; i < arr.length; i++) {

    let next = i - 1 // 由于i是没有排过序的，i前面都是排过序的，所以要对小于i索引的数值进行比较

    if(arr[i]<arr[next]){

      let temp = arr[i] // 我们将要比较的值保存在临时编变量

      while(next>=0 && temp<arr[next]){
        arr[next+1] = arr[next]
        next--
      }
      // 由于最后一个next--不符合while的执行条件，所以这里要对next+1操作，保证正确的插入位置
      arr[next+1] = temp
    }
  }
}