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

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

插入排序

插入排序（Insertion Sort）的时间复杂度是O(n ^ 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)，算法过程如其名称，最小的元素逐一上浮至数组前部：

冒泡排序示意图

代码示例

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)，其过程为，不断选择剩余元素中最小的元素，并置于剩余元素的最左（紧挨已排序元素的右侧）：

选择排序图示

代码示例

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)，不过时间复杂度就不够理想啦！