[小撒学算法]插入、冒泡与选择排序

小撒是一只好学的小鸭子,这天,小撒在学习算法

插入排序

插入排序(Insertion Sort)的时间复杂度是O(n ^ 2),其过程是不断将新元素插入到已排序部分中的正确位置:

[小撒学算法]插入、冒泡与选择排序_第1张图片
插入排序示意图

在每一次插入过程中,需要自右向左将已排序的元素与当前插入元素想比较,找到正确的插入位置:

[小撒学算法]插入、冒泡与选择排序_第2张图片
单次插入示意图

代码示例(js)

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

冒泡排序

冒泡排序(Bubble Sort)与插入排序非常类似,其时间复杂度也是O(n ^ 2),算法过程如其名称,最小的元素逐一上浮至数组前部:

[小撒学算法]插入、冒泡与选择排序_第3张图片
冒泡排序示意图

代码示例

const sort = (arr) => {
  for(let i = 0; i < arr.length - 1; i++){
    for (let j = arr.length - 1; j > i; j--) {
      if (arr[j] < arr[j - 1]) {
        swap(arr, j, j-1)
      }
    }
 }
 return arr
}

选择排序

选择排序(Selection sort)的时间复杂度同样是O(n ^ 2),其过程为,不断选择剩余元素中最小的元素,并置于剩余元素的最左(紧挨已排序元素的右侧):

[小撒学算法]插入、冒泡与选择排序_第4张图片
选择排序图示

代码示例

const sort = (arr) => {
  for (let i = 0; i < arr.length - 1; i++) {
    let indexMin = i
    for (let m = i + 1; m < arr.length; m++) {
      if (arr[m] < arr[indexMin]) indexMin = m
    }
    if (arr[i] > arr[indexMin]) {
      swap(arr, i, indexMin)
    }
  }
  return arr
}

小结

插入排序、冒泡排序、选择排序都是非常直观与朴素的排序算法,空间复杂度都是O(1),不过时间复杂度就不够理想啦!

你可能感兴趣的