大家好，我是asong。最近在逛Go仓库的时候，看到一个关于排序算法的commit，就是pdqsort排序算法。Go计划在下一个版本中支持这种排序算法。让我们详细看一下；commit地址：https://github.com/golang/go/commit/72e77a7f41bbf45d466119444307fd3ae996e257这个commit介绍了pqdsort的测试结果：在所有的benchmark测试中，pdqsort没有表现出比之前的其他算法慢。中速和10倍快）pdqsort本质上是一种混合排序算法，在不同情况下切换到不同的排序机制。这个实现的灵感来自于C++和RUST的实现。它是对C++标准库算法introsort的改进。它的理想情况下的时间复杂度是O(n)，最坏情况下是O(n*logn)，不需要额外的空间。pdqsort算法的改进在于对常见情况的特殊优化。其主要思想是不断确定当前的序列情况，然后采用不同的方法和路径来达到最优解；如果想看算法的具体实现，可以查看https://github.com/zhangyunhao116/pdqsort中的实践。它的实现是以下三种情况的连续循环：短序列：对于长度为[0,MAX_INSERTION]的输入，使用插入排序（insertsort）来排序直接返回，这里的MAX_INSERTION在我们的表现中选择为24Go语言下测试。在最坏的情况下，如果发现改进后的快速排序无效（limit==0），后续排序将使用堆排序来保证最坏情况的时间复杂度为O(n*logn)。通常，对于其他输入，使用修改后的快速排序进行排序。具体的源码实现可以自行查看，本文不再过多分析。我们来看一下pdqsort的demo：import("fmt""github.com/zhangyunhao116/pdqsort")funcmain(){x:=[]int{3,1,2,4,5,9,8,7}pdqsort.Slice(x)fmt.Printf("sort_result=%v\n",x)search_result:=pdqsort.Search(x,4)fmt.Printf("search_result=%v\n",search_result)is_sort:=pdqsort.SliceIsSorted(x)fmt.Printf("is_sort=%v\n",is_sort)}运行结果：sort_result=[12345789]search_result=3is_sort=true你的想法是什么这个排序算法的优化？让我们开始体验吧~。参考链接：https://github.com/golang/go/commit/72e77a7f41bbf45d466119444307fd3ae996e257https://www.easemob.com/news/8361https://github.com/zhangyunhao116/pdqsorthttps://arxiv.org/pdf/2106.05123.pdf
