首页 > 代码库 > 选择排序和插入排序

选择排序和插入排序

选择排序思想是:假设一组混乱数组中一个数字是排好序的,然后对其他数字逐个排序,注意他与插入排序本质区别是,选择排序没有提前退出一说,也就是说必须要全部遍历完的,而插入排序可以提前退出循环

下面选择排序代码:

let select = (arr) => {
  for (var i = 0; i < arr.length;i++) {
    for (var j = i+1; j< arr.length;j++) {
      if (arr[j] < arr[i]) {
        swap(arr, j, i)
      }
    }
  }
}

 

时间复杂度是O(n2)的

插入排序可以这么理解,假设手上只有一张牌,然后待排序的是一堆牌,依次插入到到你手中

代码如下

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

因为插入排序是可以提前退出循环的,所以插入排序优于选择排序,此外,当数组顺序性很高时候,时间复杂度插入排序要小  

选择排序和插入排序