详解Go 将在下个版本支持新型排序算法pdqsort

亲爱的编程学习爱好者，如果你点开了这篇文章，说明你对《详解Go 将在下个版本支持新型排序算法pdqsort》很感兴趣。本篇文章就来给大家详细解析一下，主要介绍一下go排序算法、pdqsort，希望所有认真读完的童鞋们，都有实质性的提高。

继Go 1.18支持泛型后，Go 将在下个版本中支持pdqsort排序算法再次引起了开发者们的热切讨论。

目前，Go仓库的最新commit中提交了pdqsort的相关功能描述：

• 在所有基准测试中，pdqsort未表现出比以前的其它算法慢；
• 在常见模式中，pdqsort通常更快（即在排序切片中快10倍）

那么pdqsort是什么呢？

pdqsort是Pattern-defeating quicksort的缩写，是一种新型的排序算法，将随机快速排序的快速平均情况与堆排序的最坏情况快速组合在一起，同时在具有特定模式的输入上实现了线性时间。 pdqsort是David Mussers introsort的扩展和改进。 在zlib许可下，所有代码都是免费的。

目前在C++和Rust中均有实现，而据不少开发者实测发现，pdqsort较常用的introsort会有较大的性能提升。

• C++ 实现: https://github.com/orlp/pdqsort
• Rust 实现: https://docs.rs/pdqsort/latest/pdqsort/

C++ 代码Demo：

#include 
#include 
#include 
#include 
#include 
 
int main()
{
    std::array s = {5, 7, 4, 2, 8, 6, 1, 9, 0, 3};
    auto print = [&s](std::string_view const rem) {
        for (auto a : s) {
            std::cout ());
    print("sorted with the standard library compare function object");
    struct {
        bool operator()(int a, int b) const { return a  b;
    });
    print("sorted with a lambda expression");
}

执行结果：

0 1 2 3 4 5 6 7 8 9 : sorted with the default operator9 8 7 6 5 4 3 2 1 0 : sorted with the standard library compare function object
0 1 2 3 4 5 6 7 8 9 : sorted with a custom function object
9 8 7 6 5 4 3 2 1 0 : sorted with a lambda expression

Rust 代码Demo：

extern crate pdqsort;

let mut v = [-5i32, 4, 1, -3, 2];
pdqsort::sort(&mut v);
assert!(v == [-5, -3, 1, 2, 4]);
pdqsort::sort_by(&mut v, |a, b| b.cmp(a));
assert!(v == [4, 2, 1, -3, -5]);
pdqsort::sort_by_key(&mut v, |k| k.abs());
assert!(v == [1, 2, -3, 4, -5]);

而就Go支持pdqsort算法，在HN上引起了不少的讨论，有人表示，我们研究排序算法这么久了，很惊讶我们还能想出能产生实际改进的优化方案。对此，你怎么看，快快上手体验一下吧。

参考链接：

https://github.com/golang/go/commit/72e77a7f41bbf45d466119444307fd3ae996e257

https://news.ycombinator.com/item?id=31106157

https://en.cppreference.com/w/cpp/algorithm/sort

好了，本文到此结束，带大家了解了《详解Go 将在下个版本支持新型排序算法pdqsort》，希望本文对你有所帮助！关注golang学习网公众号，给大家分享更多Golang知识！