跳转到内容
KN郑某某

输入关键词搜索…

↑↓ 导航
Esc

Go-三大民工排序算法

三大 (*意为连毫无闲暇时间的民工一族都耳熟能详*) 排序算法

算法基础 1 分钟阅读

三大 “民工”(意为连毫无闲暇时间的民工一族都耳熟能详) 排序算法

  • 算法实现
func SelectionSort(list []int) {
  length, idx := len(list), 0
  for left := 0; left < length; left++ {
    idx = left
    for right := left + 1; right < length; right++ {
      // 找到最小值所在的位置
      if list[right] < list[idx] {
        idx = right
      }
    }
    if idx != left {
      // 最小值所在的位置不是当前位置相同，交换
      list[left], list[idx] = list[idx], list[left]
    }
  }
}
  • 测试代码
func main() {
  list := []int{8, 4, 2, 9, 10, -3, 3, 20, 15, -1}
  SelectionSort(list)
  fmt.Println(list)
}
  • 排序结果

[-3 -1 2 3 4 8 9 10 15 20]

  • 时间复杂度

O(n^2)

  • 算法实现
func BubbleSort(list []int) {
  length := len(list)
  for left := 0; left < length; left++ {
    for right := left + 1; right < length; right++ {
      if list[left] > list[right] {
        list[left], list[right] = list[right], list[left]
      }
    }
  }
}
  • 测试代码
func main() {
  list := []int{8, 4, 2, 9, 10, -3, 3, 20, 15, -1}
  BubbleSort(list)
  fmt.Println(list)
}
  • 排序结果

[-3 -1 2 3 4 8 9 10 15 20]

  • 时间复杂度

O(n^2)

  • 算法实现
func InsertionSort(list []int) {
  length := len(list)
  for left := 0; left < length-1; left++ {
    for right := left + 1; right > 0; right-- {
      // 逐步与前面的比较
      if list[right-1] > list[right] {
        list[right-1], list[right] = list[right], list[right-1]
      } else {
        break
      }
    }
  }
}
  • 测试代码
func main() {
  list := []int{8, 4, 2, 9, 10, -3, 3, 20, 15, -1}
  InsertionSort(list)
  fmt.Println(list)
}
  • 排序结果

[-3 -1 2 3 4 8 9 10 15 20]

  • 时间复杂度

O(n^2)

评论