004.选择、冒泡、插入排序

前置知识：无

建议：会的同学直接跳过

选择排序 §

$i\backsim n-1$ 范围上，找到最小值并放在 $i$ 位置，然后 $i+1\backsim n-1$ 范围上继续

// 选择排序
func selectionSort(arr []int) {
  n := len(arr)
  for i := 0; i < n; i++ { // i ~ n - 1 找最小值
    minIdx := i
    for j := i + 1; j < n; j++ {
      if arr[j] < arr[minIdx] {
        minIdx = j
      }
    }
    arr[minIdx], arr[i] = arr[i], arr[minIdx] // 最小值放到 i 位置
  }
}

冒泡排序 §

$0\backsim i$ 范围上，相邻位置较大的数往后移，最大值最终来到 $i$ 位置，然后 $0\backsim i-1$ 范围上继续

// 冒泡排序
func bubbleSort(arr []int) {
  n := len(arr)
  for i := n - 1; i > 0; i-- {
    for j := 0; j < i; j++ { // 0 ~ i 范围上，相邻位置较大的数往后移
      if arr[j] > arr[j+1] {
        arr[j], arr[j+1] = arr[j+1], arr[j]
      }
    }
  }
}

插入排序 §

$0\backsim i$ 范围上已经有序，新来的数从右到左滑到不再小的位置插入，然后继续（“摸牌”）

// 插入排序
func insertionSort(arr []int) {
  n := len(arr)
  for i := 1; i < n; i++ { // [0, i) 已有序
    for j := i; j > 0; j-- { // 新来的数：i
      if arr[j] < arr[j-1] {
        arr[j], arr[j-1] = arr[j-1], arr[j]
      } else { // 不再小了，停！
        break
      }
    }
  }
}