Go 语言

2025年04月19日更新 4 人订阅
原价: ¥ 2 限时优惠
专栏简介 数据结构 in Golang:Hash Tables(哈希表) 算法 in Golang:Quicksort(快速排序) 算法 in Golang:Recursion(递归) 用Go语言构建分布式系统:服务注册、发现与日志管理实践 算法 in Golang:Selection sort(选择排序) Go语言之基本数据类型 深入探索Go语言:从初识到实践 实战:Go语言项目之使用JWT实现用户认证 算法 in Go:Binary Search(二分查找) 算法 in Golang:Breadth-first search(BFS、广度优先搜索) 算法 in Golang:D & C(分而治之) Go语言(Golang)编写最简单的命令行工具 深入探讨 Go 语言中的自定义 Zap 日志 Go语言详解:实现MySQL数据库的增删改查操作 深入解析Go语言Gin框架:路由注册与中间件源码剖析 Go 语言之在 Gin 框架中使用 Zap 实现高效日志管理 Go 语言中 zap 日志库的高效使用指南 Go 语言日志系统自定义:精细化日志管理与应用示例 Go 语言之搭建通用 Web 项目开发脚手架 Go语言结构体(struct)详解:定义、使用与JSON编码 探索 Go 语言的无类设计:从 Struct 到组合的优雅之道 地鼠工厂的秘密:解锁Go语言中goroutine的并发魔法 Go 并发编程实战:从互斥锁到 Goroutine 的优雅之道 用 Go 语言打造高效 TCP 扫描器:从入门到并发优化 gogen:一键生成 Go 项目,开发者的效率利器 深入剖析 Go 接口底层实现:从 eface 到 iface(基于 Go 1.24 源码) Go并发实战:5协程随机数求和 Go 开发必备:解锁 Viper 配置管理的正确姿势

算法 in Golang:Quicksort(快速排序)

算法inGolang:Quicksort(快速排序)Quicksort(快速排序)快速排序O(nlog2^n),比选择排序要快O(n²)在日常生活中经常使用使用了D&C策略(分而治之)使用Quicksort排序数组不需要排序的数组(也就是BaseCase基

算法 in Golang:Quicksort(快速排序)

Quicksort(快速排序)

  • 快速排序 O(nlog2^n),比选择排序要快 O(n²)
  • 在日常生活中经常使用
  • 使用了 D & C 策略(分而治之)

使用 Quicksort 排序数组

  • 不需要排序的数组(也就是 Base Case 基线条件):
    • [],空数组
    • [s],单元素数组
  • 很容易排序的数组:
    • [a, b],两个元素的数组,只需检查它们之间的大小即可,调换位置
  • 3 个元素的数组(例如 [23, 19, 35]):
    • 使用 D & C 策略,简化至基线条件(Base case)
  1. 从数组中随便选一个元素,例如 35,这个元素叫做 pivot(基准元素)

  2. 找到比 pivot 小的元素,找到比 pivot 大的元素,这叫做分区:[23, 19], (35), []

  3. 如果左右两个子数组已排好序(达到基线条件),结果:左边 + [pivot] + 右边

  4. 如果左右两个子数组没排好序(没达到基线条件),那么:

    quicksort(左边) + [pivot] + quicksort(右边)

使用 Quicksort 排序数组的步骤

  1. 选择一个 pivot
  2. 将数组分为两个子数组:
    1. 左侧数组的元素都比 pivot 小
    2. 右侧数组的元素都比 pivot 大
  3. 在两个子数组上递归的调用 quicksort

创建项目

~/Code/go via 🐹 v1.20.3 via 🅒 base
➜ mcd quicksort

Code/go/quicksort via 🐹 v1.20.3 via 🅒 base
➜ go mod init quicksort
go: creating new go.mod: module quicksort

Code/go/quicksort via 🐹 v1.20.3 via 🅒 base
➜ c

Code/go/quicksort via 🐹 v1.20.3 via 🅒 base
➜

main.go 代码

package main

import "fmt"

func main() {
 arr := []int{12, 87, 1, 66, 30, 126, 328, 12, 653, 67, 98, 3, 256, 5, 1, 1, 99, 109, 17, 70, 4}
 result := quicksort(arr)
 fmt.Println("result: ", result)
}

func quicksort(arr []int) []int {
 if len(arr) < 2 {
  return arr
 }

 pivot := arr[0]
 var left, right []int

 for _, ele := range arr[1:] {
  if ele <= pivot {
   left = append(left, ele)
  } else {
   right = append(right, ele)
  }
 }
 return append(quicksort(left), append([]int{pivot}, quicksort(right)...)...)
}

运行

Code/go/quicksort via 🐹 v1.20.3 via 🅒 base 
➜ go run main.go       
result:  [1 1 1 3 4 5 12 12 17 30 66 67 70 87 98 99 109 126 256 328 653]

Code/go/quicksort via 🐹 v1.20.3 via 🅒 base took 3.2s 
➜ 
点赞 1
收藏 0
分享
本文参与登链社区写作激励计划 ,好文好收益,欢迎正在阅读的你也加入。

0 条评论

请先 登录 后评论