哈嘍，大家好，我是asong。最近在逛Go倉庫時(shí)看到了一個(gè)commit是關(guān)于排序算法的，即pdqsort排序算法，Go計(jì)劃將在下一個(gè)版本中支持該排序算法，下面我們就具體來看一看這個(gè)事情;

commit地址：https://github.com/golang/go/commit/72e77a7f41bbf45d466119444307fd3ae996e257

該commit中介紹了pqdsort的測(cè)試結(jié)果：

• 在所有基準(zhǔn)測(cè)試中，pdqsort未表現(xiàn)出比以前的其它算法慢
• 常見模式中pdqsort通常更快(即在排序切片中快10倍)

pdqsort實(shí)質(zhì)為一種混合排序算法，在不同情況下切換到不同的排序機(jī)制，該實(shí)現(xiàn)靈感來自C++和RUST的實(shí)現(xiàn)，是對(duì)C++標(biāo)準(zhǔn)庫算法introsort的一種改進(jìn)，其理想情況下的時(shí)間復(fù)雜度為 O(n)，最壞情況下的時(shí)間復(fù)雜度為 O(n* logn)，不需要額外的空間。

pdqsort算法的改進(jìn)在于對(duì)常見的情況做了特殊優(yōu)化，其主要的思想是不斷判定目前的序列情況，然后使用不同的方式和路徑達(dá)到最優(yōu)解;如果大家想看一下該算法的具體實(shí)現(xiàn)，可以查看https://github.com/zhangyunhao116/pdqsort中的實(shí)踐，其實(shí)現(xiàn)就是對(duì)下面三種情況的不斷循環(huán)：

• 短序列情況：對(duì)于長(zhǎng)度在 [0, MAX_INSERTION] 的輸入，使用 insertion sort (插入排序)來進(jìn)行排序后直接返回，這里的 MAX_INSERTION 我們?cè)?Go 語言下的性能測(cè)試，選定為 24。
• 最壞情況，如果發(fā)現(xiàn)改進(jìn)的 quicksort 效果不佳(limit == 0)，則后續(xù)排序都使用 heap sort 來保證最壞情況時(shí)間復(fù)雜度為 O(n*logn)。
• 正常情況，對(duì)于其他輸入，使用改進(jìn)的 quicksort 來排序。

具體的源代碼實(shí)現(xiàn)可以自行查看，本文就不過多分析了，下面我們來看一下pdqsort的demo：

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)
}

運(yùn)行結(jié)果：

sort_result = [1 2 3 4 5 7 8 9]
search_result = 3
is_sort = true

對(duì)于此次排序算法優(yōu)化你們有什么想法?快快上手體驗(yàn)一下吧～。

參考鏈接：

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