排序算法

选择排序

func selectSort(arr []int) {
 // 遍历n轮
 for i := 0; i < len(arr); i++ {
  // 找到当前数组范围内的最小值的小标
  minIndex := i
  for j := i; j < len(arr); j++ {
   // 找到最小的
   if arr[minIndex] > arr[j] {
    minIndex = j
   }
  }
  // 如果最小值下标和头部下标不同就进行交换
  if minIndex != i {
   arr[i], arr[minIndex] = arr[minIndex], arr[i]
  }
 }
}

冒泡排序

func bubbleSort(arr []int) {
 // 一共需要遍历n-1轮
 for i := 0; i < len(arr); i++ {
  // 因为每一轮都会把最大的值放到末尾，所以下次遍历的时候，就不用遍历到排序好的下标处了
  // 所以这里用了len(arr) - 1 - i
  for  j := 0; j < len(arr) - 1 - i; j++ {
   if arr[j] > arr[j + 1] {
    // 交换位置
    arr[j],arr[j+1] = arr[j+1],arr[j]
   }
  }
 }
}

归并排序

func mergeSort(nums []int) []int {
 // 递归的出口，数组中剩一个元素的时候返回
 if len(nums) == 1 {
  return nums
 }
 /** ================分================*/
 // 找中点
 mid := len(nums) / 2
 // 分为左半部分
 left := nums[0:mid]
 // 分为右半部分
 right := nums[mid:]
 // 递归进行分，在这里分好的是已经执行了下面“合”操作的，所以已经是排序好的数组了
 orderLeft := mergeSort(left)
 orderRight := mergeSort(right)
 /** ================合================*/
 // 创建数组进行接收
 res := make([]int, 0, len(orderLeft)+len(orderRight))
 // 遍历
 i, j := 0, 0
 for i < len(orderLeft) && j < len(orderRight) {
  if orderLeft[i] > orderRight[j] {
   res = append(res, orderRight[j])
   j++
  } else {
   res = append(res, orderLeft[i])
   i++
  }
 }
 for i < len(orderLeft) {
  res = append(res, orderLeft[i])
  i++
 }
 for j < len(orderRight) {
  res = append(res, orderRight[j])
  j++
 }
 // 返回结果
 return res
}

快速排序

// 为了方便理解 没有在原数组上操作
func quickSort(arr []int) []int {
 // 如果当前数组只要一个值或者没有值，直接返回即可
 if len(arr) <= 1 {
  return arr
 }
 // 左侧分区
 left := make([]int, 0, len(arr))
 // 右侧分区
 right := make([]int, 0, len(arr))
 // 基准点
 base := arr[0]
 // 从当前数组的第二项开始与基准点进行比较
 for i := 1; i < len(arr); i++ {
  // 如果比基准点小，就放入左侧
  if arr[i] < base {
   left = append(left, arr[i])
  } else {
   // 比基准点大，就放入右侧
   right = append(right, arr[i])
  }
 }
 // 进行递归
 orderLeft := quickSort(left)
 orderRight := quickSort(right)
 temp := append(orderLeft, base)
 return append(temp, orderRight...)
 // 讲排序好的数组组合在一起
}

// 在原数组上操作
func quickSort(arr []int) []int {
 // TODO
}

插入排序

func insertSort(arr []int) {
 for i := 1; i < len(arr); i++ {
  // 选择一个值与他前面的值进行比较
  p := i
  tmp := arr[p]
  // 遍历在他前面的所有值
  for p > 0 {
   // 如果选择的这个值要小，就将前面的值后移
   if tmp < arr[p-1] {
    arr[p] = arr[p-1]
   } else {
    // 否则就跳出循环
    break
   }
   // 将坐标不断前移比较
   p -= 1
  }
  // 最后p就是空出的位置
  arr[p] = tmp
 }
}