Go1.19 排序算法设计实践 经典排序算法对比

详解经典排序算法

01 为什么要学习数据结构与算法

抖音直播排行榜功能 案例

规则：某个时间段内，直播间礼物数TOP10房间获得奖励，需要在每个房间展示排行榜解决方案

•礼物数量存储在Redis-zset中，使用skiplist使得元素整体有序
•使用Redis集群，避免单机压力过大，使用主从算法、分片算法
•保证集群原信息的稳定，使用一致性算法
•后端使用缓存算法(LRU)降低Redis压力，展示房间排行榜数据结构和算法几乎存在于程序开发中的所有地方

讲师 张云浩 这个大佬的 团队提出的 算法 被官方采纳 应用于1.19

02 经典排序算法

Insertion Sort 插入排序

时间复杂度：

Best: 有序情况

Avg: 是翻转的对数log决定的，大家也可以看看详细解析

algorithm - Why is insertion sort Θ(n^2) in the average case? - Stack Overflow

Worst: 逆序

Quick 快速排序

Best: 每一次选择的轴点恰好是中位数，这样每次分割都能分割成 两个几乎相等的数组

Worst: 每次只将一个元素放到最终位置，例如选择的轴点都是已知序列的最小元素

Heap 堆排序

经典算法理论印象

实际场景

random

Selected

从零开始打造 pdqsort

pdqsoer—简介

不稳定：可能会对值相等的元素调整位置

pdqsort- version1

结合三种排序方法的优点

•对于短序列（小于一定长度）我们使用插入排序
•其他情况，使用快速排序来保证整体性能
•当快速排序表现不佳时，使用堆排序来保证最坏情况下时间复杂度仍然为O(n*logn)

Q&A

1.短序列的具体长度是多少呢？

12~32，在不同语言和场景中会有不同，在泛型版本根据测试选定24

2.如何得知快速排序表现不佳，以及何时切换到堆排序？

当最终pivot的位置离序列两端很接近时（距离小于length/8）判定其表现不佳，当这种情况的次数达到limit(即bits.Len(length))时，切换到堆排序

pdqsort- version2

pdqsort—final version（Go1.19 default）

高性能的排序算法是如何设计的？

根据不同情况选择不同策略，取长补短

生产环境中使用的的排序算法和课本上的排序算法有什么区别？

理论算法注重理论性能，例如时间、空间复杂度等。生产环境中的算法需要面对不同的实践场景，更加注重实践性能

Go语言(<=1.18)的排序算法是快速排序么？

实际一直是混合排序算法，主体是快速排序。Go<=1.18时的算法也是基于快速排序，和pdqsort的区别在于fallback时机、pivot选择策略、是否有针对不同pattern优化等

非常感谢您阅读到这里，创作不易！如果这篇文章对您有帮助，希望能留下您的点赞👍 关注💖 收藏 💕评论💬感谢支持！！！

听说三连的人都能 上岸 进入大厂 年入百w