pattern-defeating-quicksort簡介

pdqsort是一種不穩(wěn)定的混合排序算法，采用了快速排序和插入排序的結合，以避免快速排序在小數組上的性能下降。

pdqsort還使用了一些模式避免技術，以減少分支預測錯誤和緩存行不命中的次數。這些優(yōu)化使得pdqsort在各種情況下都表現良好，尤其是對于大型、隨機分布的數據集。

pdqsort已經被廣泛應用于各種編程語言和庫中，如Go1.19 Rust、C++等。

復雜度
最好的情況：O(n)
平均情況：O(n*logn)
最壞的情況：O(n*logn)

pdqsort的不同版本

第一個版本

應對短序列時，算法會使用插入排序，中序列或長序列則使用快速排序；
如果快速排序效果表現不佳時，則切換成堆排序

何時會認為快速排序的效果表現不佳？

當計算累計mm 輪（這里的 m=f(n)m=f(n) ， f(n)f(n) 是一個關于序列長度的函數）選取的 pivot 在本輪結束后的位置離數組兩端距離小于 n/8n/8 時，即判定快速排序效果表現不好。

總結：結合插入排序、快速排序和堆排序三種排序優(yōu)勢。

第二個版本

在第一個版本中，由于快速排序的速度制約著pdqsort的整體排序效率。

第二個版本主要優(yōu)化快速排序，具體是優(yōu)化快速排序中的選取基數pivot的代碼。

關于pivot的選擇
使用首個元素作為 pivot：業(yè)務簡單，但往往表現不佳，特別是在數組有序的情況。
遍歷數組，尋找數組中位數：遍歷迭代的代價高，綜合表現得性能不好，盡管能帶來很不錯的效果。
平衡尋找 pivot 所需要的開銷及 pivot 帶來的性能優(yōu)化：尋找近似中位數。
前兩個屬于比較極端的選法，而算法需要權衡pivot選取的有效性，也要考慮選取pivot的代價，第三種就是這樣做的。

近似中位數選取方法如下：

n?8n?8 時在純快排里pivot會直接選固定元素，但在pdqsort里這種規(guī)模的序列會直接用插入排序。
n?50n?50 時，采樣三個元素，選擇三個元素中的中位數。
n>50n>50 時，采樣九個元素，選擇九個元素中的中位數。

第三個版本

主要解決如何優(yōu)化重復元素很多的情況

重復元素較多的情況(partitionEqual)

當檢測到此時的 pivot 和上次相同時(發(fā)生在 leftSubArray)，即partition進行了無效分割，此時認為pivot的值為重復元素，使用 partitionEqual 將重復元素排列在一起，減少重復元素對于 pivot 選擇的干擾
當 pivot 選擇策略表現不佳時，隨機交換元素

避免一些極端情況使得 QuickSort 總是表現不佳，以及一些黑客攻擊情況

pdqsort是一種新的排序算法，專為Go語言而設計。它采用了分治的策略，將數組分成小塊進行排序，然后再合并這些塊。這種策略使得pdqsort在處理大規(guī)模數據時表現出色。此外，pdqsort還具有自適應的特性，可以根據輸入數據的特點進行優(yōu)化，從而提高排序的效率。pdqsort的設計和實現經過了精心的打造，旨在提供高效且穩(wěn)定的排序算法。對于Go語言的開發(fā)者來說，pdqsort是一個非常有價值的選擇。它不僅可以提高排序的效率，還可以減少開發(fā)者的工作量。因此，pdqsort是Go語言新寵，值得開發(fā)者們去嘗試和使用。

到此這篇關于Go語言新寵：pdqsort排序算法的完美打造的文章就介紹到這了,更多相關打造Go語言的pdqsort排序算法內容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！