小撒是一只好學的小鴨子，這天，小撒在學習算法

插入排序

插入排序（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)，不過時間復雜度就不夠理想啦！