关于golang:Go语言将引入新型排序算法pdqsort

原文链接：Go语言将引入新型排序算法：pdqsort

asongGocommitpdqsortGo

commit

<img src=”https://p3-juejin.byteimg.com/tos-cn-i-k3u1fbpfcp/42c63502e8f44a87a904ad340e934d63~tplv-k3u1fbpfcp-zoom-1.image” alt=”截屏2022-05-06 下午1.37.10″ style=”zoom:67%;” />

commitpqdsort

pdqsortpdqsort

pdqsortC++RUSTC++introsort

pdqsorthttps://github.com/zhangyunhao116/pdqsort

• 短序列状况：对于长度在 [0, MAX_INSERTION] 的输出，应用 insertion sort (插入排序)来进行排序后间接返回，这里的 MAX_INSERTION 咱们在 Go 语言下的性能测试，选定为 24。
• 最坏状况，如果发现改良的 quicksort 成果不佳(limit == 0)，则后续排序都应用 heap sort 来保障最坏状况工夫复杂度为 O(n*logn)。
• 失常状况，对于其余输出，应用改良的 quicksort 来排序

pdqsort

import (
    "fmt"

    "github.com/zhangyunhao116/pdqsort"
)

func main() {
    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 = [1 2 3 4 5 7 8 9]
search_result = 3
is_sort = true

对于此次排序算法优化你们有什么想法？快快上手体验一下吧～。

参考链接：

• https://github.com/golang/go/…
• https://www.easemob.com/news/…
• https://github.com/zhangyunha…
• https://arxiv.org/pdf/2106.05…

好啦，本文到这里就完结了，我是asong，咱们下期见。

欢送关注公众号：Golang梦工厂