pattern-defeating-quicksort簡介

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

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

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

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

pdqsort的不同版本

第一個版本

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

何時會認為快速排序的效果表現(xiàn)不佳？

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

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

第二個版本

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

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

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

近似中位數(shù)選取方法如下：

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

第三個版本

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

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

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

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

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

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

最新評論