数据结构 Sort

数据结构与算法回顾（七）：Golang 中的 Sort 算法实现解析

排序算法回顾

Posted by pandaychen on August 1, 2021

0x00 前言

本文分析下golang的Sort算法实现

0x01 sort的典型使用

Golang 的 sort.Sort 使用了一个接口类型 sort.Interface 来指定通用的排序算法和可能被排序到的序列类型之间的约定。这个接口的实现由序列的具体表示和它希望排序的元素决定，通常排序的对象是Slice

case1：[]int排序

对 []int slice序列按照从小到大升序排序

type IntSlice []int

func (s IntSlice) Len() int           { return len(s) }
func (s IntSlice) Less(i, j int) bool { return s[i] < s[j] }
func (s IntSlice) Swap(i, j int)      { s[i], s[j] = s[j], s[i] }
func main() {
        s := []int{4, 5, 1, 7, 2, 9}
        sort.Sort(IntSlice(s))
        fmt.Println(s)
}

case2：查找

可以利用sort.Search方法对有序数据进行查找，注意要遵循：使用sort.Search时，入参条件是根据要查找的序列是升序序列还是降序序列来决定的，如果是升序序列，则传入的条件应该是>=目标元素值；如果是降序序列，则传入的条件应该是<=目标元素值

func main() {
        arrInts := []int{13, 35, 57, 79}
        findPos := sort.Search(len(arrInts), func(i int) bool {
                //return arrInts[i] >= 35 //true
                return arrInts[i]==35 //wrong! 输出不符合预期
        })

        fmt.Println(findPos)
        return
}

0x02 分析

sort 包内部实现了四种基本的排序算法：

  • 插入排序（insertionSort）
  • 归并排序（symMerge）
  • 堆排序（heapSort）
  • 快速排序 （quickSort）

0x0 参考

CATALOG
    FEATURED TAGS
    Latex gRPC 负载均衡 OpenSSH Authentication Consul Etcd Kubernetes 性能优化 Python 分布式锁 WebConsole 后台开发 Golang OpenSource Nginx Vault 网络安全 Perl 分布式理论 Raft 正则表达式 Redis 分布式 限流 go-redis 微服务 反向代理 ReverseProxy Cache 缓存 连接池 OpenTracing GOMAXPROCS GoMicro 微服务框架 日志 Pool Kratos Hystrix 熔断 并发 Pipeline 证书 Prometheus Metrics Breaker 定时器 Timer Timeout Kafka Xorm MySQL Fasthttp bytebufferpool 任务队列 队列 异步队列 GOIM Pprof errgroup consistent-hash Zinx 网络框架 设计模式 HTTP Gateway Queue Docker 网关 Statefulset NFS Machinery Teleport Zero Trust Oxy 存储 Confd 热更新 OAuth SAML OpenID Openssl AES 微服务网关 IM KMS 安全 数据结构 hashtable Sort Asynq 基数树 Radix Crontab 热重启 系统编程 sarama Go-Zero RDP VNC 协程池 UDP hashmap 网络编程 自适应技术 环形队列 Ring Buffer Circular Buffer InnoDB timewheel GroupCache Jaeger GOSSIP CAP Bash websocket 事务 GC TLS singleflight 闭包 Helm kubernetes network iptables MITM HTTPS tap tun 路由 wireguard Tun gvisor Git NAT 协议栈 Envoy FRP DPI gopacket DNS GoZero Gost
    FRIENDS