快捷導(dǎo)航

Go語(yǔ)言新寵：pdqsort排序算法的完美打造

更新時(shí)間：2023年10月03日 11:11:49 作者：51鱷魚兒

pdqsort是一種新的排序算法,特別適用于Go語(yǔ)言,它是由Go語(yǔ)言團(tuán)隊(duì)開發(fā)的,旨在提供高效且穩(wěn)定的排序算法,pdqsort采用了一種分治的策略,將數(shù)組分成小塊進(jìn)行排序,然后再合并這些塊,需要的朋友可以參考下

pattern-defeating-quicksort簡(jiǎn)介

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

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

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

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

pdqsort的不同版本

第一個(gè)版本

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

何時(shí)會(huì)認(rèn)為快速排序的效果表現(xiàn)不佳？

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

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

第二個(gè)版本

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

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

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

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

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

第三個(gè)版本

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

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

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

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

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

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

您可能感興趣的文章: