前言

說到排序算法，很多同學會想到快速排序、堆排序、冒泡排序等熟悉的算法。比較了解的同學可能也見過Python的timsort、SinoSort等排序算法。

但是我們也有很多疑問，比如Go語言中使用的快速排序和我們書本上學到的快速排序有什么區別？如果我們自己寫一個快線，會比Go語言本身快嗎？排序算法領域有什么最新進展？有什么算法是最快的？

本文將介紹字節跳動-語言團隊's在Go語言中排序算法的實踐。我們使用通用版本的pdqsort算法Go1.18，并實現了一個在幾乎所有情況下都比標準庫API快 2x ~ 60x的算法庫。

此項改動已經被社區采納合并進入 Go runtime 當中,作為默認的不穩定排序算法，有望在Go 1.19中與大家見面，其中非泛型版本位于標準庫排序，泛型版本位于exp/slices。

提案： https://github.com/golang/go/issues/50154

臨時項目地址：https://github.com/zhangyunhao116/pdqsort

簡介

Go，Rust，C默認的不穩定排序算法名為quicksort，但本質是混合排序算法。雖然他們在大多數情況下會使用快速排序，但在不同的情況下也會切換到其他排序算法。

不穩定排序算法是指在排序過程中，值相等的元素可能會互相交換位置。

一般來說，常見的混合排序算法在元素較少的序列中會切換到插入排序(該值一般為16 ~ 32)。雖然插入排序的時間復雜度為O (n 2)，但在元素較少的情況下，其性能基本上超越了其他排序算法，因此常被用于混合排序算法中。

在其他情況下，默認使用快速排序。但是快速排序在某些情況下可能會達到最壞的時間復雜度O(n ^ 2)，這是因為pivot選擇的問題(有些序列pivot選擇不好，導致性能快速下降)。為了保證快速排序的最壞情況，我們的時間復雜度仍然是O(n* logn)。大多數混合排序算法在某些情況下會轉向堆排序，因為堆排序在最壞情況下的時間復雜度仍能保持O(n* logn)。

總之，目前流行的不穩定排序算法，基本上都是針對不同的情況采用不同的方式進行排序，以達到最優解。我們今天介紹的pdqsort也是這種思想的延伸。

先驗知識

介紹了一些常見的基本排序算法及其特點。

快速排序(經典)

平均情況：O(n*logn) Bad-case:O(n^2)

經典的快速排序主要采用分而治之的思想。具體過程是通過選擇一個支點(錨點)，將一個數組劃分為不同的子數組。選擇一個樞軸后，該數組中樞軸左側的元素都小于樞軸，樞軸右側的元素都大于樞軸。因此，在樞軸的兩側形成兩個子陣列，然后對這些子陣列進行相同的操作(選擇樞軸，然后進行分割)。當一個子數組只有一個元素時，它是有序的，然后它可以退出循環。如此反復，最后得出整體順序。

我們可以觀察到經典快速排序的主要過程是兩個步驟：

選擇pivot:選擇一個透視。

Partition:使用pivot對數組進行分區。

一般來說，快速分揀性能的關鍵在于pivot,的選擇，而支點的選擇直接決定了分揀的速度。

為什么 pivot 選定為中位數使得快排效率最高？

詳細解釋可以參考：https://en.wikipedia.org/wiki/Quicksort#Formal_analysis。簡單來說，pivot 如果選定為中位數，則大部分情況下每次 partition 都會形成兩個長度基本相同的 sub-arrays，我們只需要 logn 次 partition 就可以使得 array 完全有序，此時時間復雜度為 O(n* logn)。在最壞情況下，我們需要 n-1 次 partition （每次將長度為 L 的 array 分為長度為 1 和 L - 1 的兩個 sub-arrays）才能使得 array 有序，此時時間復雜度為 O(n^2)。

我們為何不直接尋找 array 真正的 median？

原因是因為 array 的長度太長的話，尋找真正的 median 是一個非常昂貴的操作（需要存儲所有的 items），相比于尋找一個近似的 median 作為 pivot 會消耗更多的資源，如果找到正確 median 的消耗比使用一個近似 median 高的話，這就是一個負優化。折中的方案就是使用一個高性能的近似 median 選擇方案。

基本所有針對 quicksort 的改進方案，都是通過改造這兩步得到的，例如第一步可以使用多種不同的 pivot 選擇方案（見附錄），第二步則有諸如 BlockQuickSort 這樣通過減少分支預測來提升性能的方案。

Insertion sort

插入排序的主要想法是，每一次將一個待排序的元素插入到前方已經排序好的序列中，直到插入所有元素。盡管其平均時間復雜度高達 O(n^2)，但是在 array 長度較短（這個值一般是 16 ~ 32）的情況下，在實際應用中擁有良好的性能表現。

Heap sort

堆排序是利用堆結構設計出來的一種排序算法。這個算法有一個非常重要的特性，其在最壞情況下的時間復雜度仍然為 O(n* logn)。故而很多混合排序算法利用了這一特性，將堆排序作為 fall back 的排序算法，使得混合排序算法在最壞情況下的理論時間復雜度仍然為 O(n* logn)。

pdqsort (pattern-defeating quicksort)

論文地址：https://arxiv.org/pdf/2106.05123.pdf

pdqsort (pattern-defating quicksort) 是 Rust、C++ Boost 中默認的 unstable 排序算法，其實質為一種混合排序算法，會在不同情況下切換到不同的排序機制，是 C++ 標準庫算法 introsort 的一種改進?？梢哉J為是 unstable 混合排序算法的較新成果。

其理想情況下的時間復雜度為 O(n)，最壞情況下的時間復雜度為 O(n* logn)，不需要額外的空間。

pdqsort 的主要改進在于，其對 common cases （常見的情況）做了特殊優化。因此在這些情況下性能超越了之前算法，并且相比 introsort 在隨機序列的排序性能基本保持了一致。例如當序列本身有序、完全逆序、基本有序這些情況下都超越了大部分算法。其主要的思想是，不斷判定目前的序列情況，然后使用不同的方式和路徑達到最優解。

這里的算法細節描述的是 https://github.com/zhangyunhao116/pdqsort 中的實踐，其大致相當于論文中的 PDQ 算法（沒有來自 BlockQuickSort 的優化），并且加入了一些參數調整以及借鑒了部分其他 pdqsort 的實踐優化。

注意，不同 pdqsort 實踐中會有一些細微差異（因為語言以及接口的關系），不過其總體思想是一致的。

pdqsort C++ 版本性能對比，位于 https://github.com/orlp/pdqsort

整體流程

為了更好地解析 pdqsort 算法，我們先來描述下其主要流程。pdqsort 就是下面三種情況的不斷循環，根據序列長度以及是否是最壞情況，每個 array 都會使用下面三種方法之一進行排序（有優先級，盡可能使用排在前面的方式）

1. 短序列情況，對于長度在 [0, MAX_INSERTION] 的輸入，使用 insertion sort （插入排序）來進行排序后直接返回，這里的 MAX_INSERTION 我們在 Go 語言下的性能測試，選定為 24。
2. 最壞情況，如果發現改進的 quicksort 效果不佳（limit== 0），則后續排序都使用 heap sort 來保證最壞情況時間復雜度為 O(n*logn)。
3. 正常情況，對于其他輸入，使用改進的 quicksort 來排序，這里的算法分幾步，后續內容會詳細介紹部分步驟。

圖中淺黃色虛線框代表此步驟為可選項，即算法會根據情況（以下變量）來決定是否執行。

下列變量代表 pdqsort 進行本次循環排序的情況，用于幫助算法來猜測需要排序的 array 的狀態，來決定某些步驟是否需要進行

• wasBalanced: Bool, 代表上次 partition 是否平衡。在 pivot 和真正的 median 很接近時我們認為是平衡的（true），此變量可以用 partition 后的 pivot index 同 array 兩端的距離來判定。
• wasPartitioned: Bool, 如果為真，則代表上次 partition 沒有交換任何元素（即上次 partition 分割的是一個本身已經有序的 array）。
• limit: int，如果為 0，則后續對 unsorted array 的排序都會使用 heap sort 而不是 quick sort。這種情況發生在 quicksort 有很多次選擇的 pivot 和真正的 median 差距很大，從而導致 partition 后的兩個 sub-arrays 長度相差較大的場景中。limit的初始值是根據待排序 array 的長度計算出來的，每次發現快排策略效果不佳時，即 !wasBalanced為真，則使得 limit減小 1。

3-1. 應對可能的最壞情況，即實現中的breakPatterns。此時會判斷 wasBalanced 是否為 true，如果不平衡（false），則隨機交換幾個元素，破壞一些可能造成 pivot 與 median 相差較大的特殊情況。

3-2. pivot 的選擇，即實現中的 choosePivot。函數同時返回兩個值，pivotidx 和 likelySorted，前者是 pivot 在此 array 的 index（索引），后者代表著選擇 pivot 的過程中，是否可以大概率認定這個 array 已經為有序。

3-3. 應對幾乎有序的情況，即實現中的 partialInsertionSort。如果 wasBalanced && wasPartitioned && likelySorted為 true，則代表此 array 有非常大的可能是一個有序序列。此時我們使用 partial insertion sort 的排序算法，其原理和 insertion sort 大致相當，只是多了一個嘗試次數，即只會對有限的元素進行插入排序，增加這個限制是為了避免猜測錯誤導致消耗大量時間。如果達到嘗試次數時 array 仍未有序，則退出。如果在嘗試次數之前發現所有元素有序，則可以直接返回。

3-4. 應對重復元素較多的情況，即實現中的 partitionEqual。如果 pred 存在，并且和本次選中的 pivot 值相等（pred 是之前 array 的 pivot，即目前 array 中的最小值，因為與 pivot 重復的元素只可能出現在 partition 后的兩個 sub-arrays 其中之一），說明重復元素很可能較多，則調用 partitionEqual然后繼續進行下次循環，使用這種方法將重復元素提前放到一起，因為多次選定重復元素作為 pivot 會使得 partition 的效率較低。

3-5. partition，使用 pivot 來分割 array，即實現中 partition。此函數和一般快排的 partition 相比基本相同，區別在于其會檢測序列是否本身就是有序的（即 partition 時沒有交換任何元素）。

實現細節

breakPatterns (3-1)

這一步的作用是解決一些會導致現有 pivot 選擇方案表現很差的情況，所以當上次 partition 的 pivot 選擇不好時（表現為最終 pivot 的位置離 array 兩端之一很近），此時會隨機交換幾個元素來避免一些極端情況。同時，此步驟還會將 limit減去 1，說明上次 pivot 的選取方案不夠好（當 limit為 0 時使用 heapsort 而不是快排方案來進行排序）。

pivot 選擇 (3-2)

附錄中有關于 pivot 選擇方案的詳細介紹。

假設 array 的長度為 L，SHORTEST_MEDIAN_OF_MEDIANS 值為 50。這里根據長度分為三種情況：

1. L 位于 [0,8): 直接取固定值作為 pivot，即 L/4 * 2
2. L 位于 [8,SHORTEST_MEDIAN_OF_MEDIANS): 使用 medians of three 方法采樣 3 個元素篩選 pivot，即 L/4* 1 L/4* 2 L/4* 3 的中間值
3. L 位于 [SHORTEST_MEDIAN_OF_MEDIANS, ∞): 使用 Tukey’s median of medians 采樣 9 個元素得到一個近似中間值

此方法還會判斷這個 array 是否很可能已經有序，例如當第三種情況時，如果發現 a a-1 a+1 這三個值中，a 恰好是中間值（b,c 也同樣如此），則說明元素在這些地方都局部有序，所以這個 array 很可能是已經有序的。如果每次都發現，a a-1 a+1 這三個值都是逆序排列（b,c 也同樣如此），則說明元素在這些地方都局部逆序，整個 array 很可能是完全逆序的。此時的策略是將整個 array 翻轉，這樣有很大概率使得整個 array 幾乎有序。

Go 語言環境下的實踐考量

Go 1.18 泛型對于排序算法的影響

Go 1.18 的泛型在這種情況下有較大的性能提升并且增加了可維護性，同樣的算法在經過泛型改造后能得到 2x的性能提升。這一點我們通過觀察 pdqsort 泛型版本，以及 pdqsort (with sort.Interface) 的版本性能對比可以觀察出來。

在可維護性方面，通過泛型的類型約束抽象了所有可比對的基本類型，不需要使用復雜的代碼生成技術。

在性能方面，泛型由于有了類型參數，可以在編譯期生成大量代碼，免去了使用 sort.Interface帶來的抽象開銷。

pdqsort 相比于 Go 原有算法的優勢

在純粹的算法層面，即 pdqsort (with sort.Interface) ，pdqsort 在完全隨機的情況下和原有算法（類似于 IntroSort）性能幾乎一致（非泛型版本，因為需要兼容 sort.Interface）。在常見的場景下（例如序列有序|幾乎有序|逆序|幾乎逆序|重復元素較多）等情況下，會比原有的算法快 1 ~ 30倍。

因此，我們同樣向 Go 官方提議將 pdqsort 應用在 sort.Sort 中，相關的 issue 討論位于：https://github.com/golang/go/issues/50154

Go 原有的算法類似于 introsort，其通過遞歸次數來決定是否切換到 fall back 算法，而 pdqsort 使用了另一種計算方式（基于序列長度），使得切換到 fall back 算法的時機更加合理。

為什么禁用來自 BlockQuickSort 的優化

因為 BlockQuickSort 的優化基本來自減少分支預測，原理是在 partition 一個長序列的時候，先存儲需要交換的元素，后續統一放到真正的序列中。經過實際性能測試，發現這一優化在 Go 上并不成立，甚至是一個負優化。原因可能由于 Go 是一門 heap-allocate 的語言，對于此類優化并不敏感。并且對于減少分支預測，Go 的編譯器在某些情況下并不能優化到相應指令（CMOV）。

總結

目前大部分工業界使用的 unstable 排序算法，基本上都從過去教科書中單一的排序算法轉變成混合排序算法，來應對實踐場景中各式各樣的序列。

pdqsort 依靠其在常見場景相比之前算法的性能優勢，逐漸成為 unstable 排序算法的主流實現?；?Go1.18 帶來的泛型，使得排序算法的實現被大大簡化，也給予了我們實現新算法的可能。但是 pdqsort 也不是萬能靈藥，在某些情況下，其他的算法依然保持著優勢（例如 Python 標準庫的 timsort 在混合升序&&降序的場景優于 pdqsort）。不過在大部分情況下，pdqsort 依靠其對于不同情況的特定優化，成為了 unstable 算法較好的選擇。

附錄

quicksort pivot 方案對比

這里簡單介紹不同的 pivot 選擇方案。最好的 pivot 選擇方案就是使用一個高性能的近似 median 選擇方案，在準確度和性能上達到平衡。假設我們需要排序的元素為 [4,3,2,1]，我們需要將其排列為升序，即 [1,2,3,4]。

選擇首個元素

這是我們實現快排時最簡單的方法，即選取 array 的首個元素作為 pivot。

• [4,3,2,1]。選定 4 為 pivot，由于左邊沒有元素，所以會從最右邊開始找，找到第一個比 4 小的元素，即 1 作交換。
• [1,3,2,4]。選定 1 為 pivot，同理。希望從右邊找到第一個比 1 小的元素，由于 1 已經是最小的值，此輪不會交換任何元素。
• [1,3,2,4]。選定 3 為 pivot，同理。將 2 和 3 互換。
• [1,2,3,4]。得到結果。

可以看到，選擇首個元素的方式在 array 為逆序的情況下，每輪 partition 只將問題的規模減小了 1，即每次只能確定一個元素的最終位置。這種簡單的方法在面對極端情況時效果并不好，在完全逆序的情況下達到了快排的最壞情況。

median of three

這個方法是分別取最左邊、最右邊、中間三個值，然后選出其中間值作為 pivot。例如 [4,3,2,1]，我們會選取 4 3 1然后選擇其中的 3作為 pivot。這種方式相比于首個元素的方式會更加合理，因為采樣了多個元素，不容易受到一些極端情況的影響，往往會比首個元素的方式有更好的效果。

stackoverflow discussion:

https://stackoverflow.com/questions/7559608/median-of-three-values-strategy

median of medians

這個方法的原理其實和 median of three 相似，不同的地方在于加大了 pivot 的采樣范圍，在 array 長度較長的情況下理論表現會更好。其采樣步驟是先將 array 分為 n/5 個 sub-arrays，n 為 array 的長度。然后將這些 sub-arrays 的 medians 都取出，選取這些 medians 中的 median，同樣的方式如此反復，最后得到一個 median of medians 作為最后的 pivot。

stackoverflow discussion:

https://stackoverflow.com/questions/5605916/quick-sort-median-selection

Median-finding Algorithm:

https://brilliant.org/wiki/median-finding-algorithm/#citation-1

John Tukey’s median of medians

此方法其實是 median of three 的改進，我們在 median of three 會取三個元素，而 Tukey’s median of medians 會取三個元素及其相鄰兩個元素的 median（例如 median of three 取了 a,b,c 則此方案會選擇 a-1 a a+1 取這三個值的 median），然后再取這個三個 medians 的 median。即此方案會采樣其中 9 個元素，相比于 median of three 多了三倍的采樣率，所以此方法也叫做 Tukey’s ninther。

See

https://www.johndcook.com/blog/2009/06/23/tukey-median-ninther/

標簽：算法 元素 情況下