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

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

該commit中介紹了pqdsort的測試結果：

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

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

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

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

具體的源代碼實現可以自行查看，本文就不過多分析了，下面我們來看一下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)
}

運行結果：

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

對于此次排序算法優化你們有什么想法?快快上手體驗一下吧～。

參考鏈接：

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