[算法] 插入排序

[david2tdw]

插入排序

插入排序 的思路是选取遍历元素，依次向前比较每一项，直到找到比他小的元素，将比他大的元素向后移动，将当前元素temp插入此位置。

把当前项temp拿出来，然后依次从当前项往前遍历，如果遍历元素比当前项temp大，就把遍历元素往后移动一位，如果遍历元素不比当前项大，则把当前项temp插入到此位置。

// 生成指定个数的随机数组
const generateArr = (num = 10) => {
  let arr = []
  for (let i = 0; i < num; i++) {
    let item = Math.floor(Math.random() * (num + 1)) // 返回小于等于x的最大整数:
    arr.push(item)
  }
  return arr
}

function insertionSort(arr) {
  let len = arr.length,
    j,
    temp
  for (let i = 1; i < len; i++) {
    j = i
    temp = arr[i]
    while (j > 0 && arr[j - 1] > temp) {
      arr[j] = arr[j - 1]
      j--
    }
    arr[j] = temp
  }
  return arr
}

const arr = generateArr(60)
console.time()
const result = insertionSort(arr)
console.timeEnd()
// console.log(result)