哈喽，大家好，我是asong。最近在逛Go仓库时看到了一个commit是关于排序算法的，即pdqsort排序算法，Go计划将在下一个版本中支持该排序算法，下面我们就具体来看一看这个事情;,commit地址：https://github.com/golang/go/commit/72e77a7f41bbf45d466119444307fd3ae996e257,该commit中介绍了pqdsort的测试结果：,pdqsort实质为一种混合排序算法，在不同情况下切换到不同的排序机制，该实现灵感来自C++和RUST的实现，是对C++标准库算法introsort的一种改进，其理想情况下的时间复杂度为 O(n)，最坏情况下的时间复杂度为 O(n* logn)，不需要额外的空间。,pdqsort算法的改进在于对常见的情况做了特殊优化，其主要的思想是不断判定目前的序列情况，然后使用不同的方式和路径达到最优解;如果大家想看一下该算法的具体实现，可以查看https://github.com/zhangyunhao116/pdqsort中的实践，其实现就是对下面三种情况的不断循环：,具体的源代码实现可以自行查看，本文就不过多分析了，下面我们来看一下pdqsort的demo：,运行结果：,对于此次排序算法优化你们有什么想法?快快上手体验一下吧～。,https://github.com/golang/go/commit/72e77a7f41bbf45d466119444307fd3ae996e257,https://www.easemob.com/news/8361,https://github.com/zhangyunhao116/pdqsort,https://arxiv.org/pdf/2106.05123.pdf
© 版权声明
文章版权归作者所有，未经允许请勿转载。
">