Go語言新寵：pdqsort排序算法的完美打造
pattern-defeating-quicksort簡介
pdqsort是一種不穩(wěn)定的混合排序算法，采用了快速排序和插入排序的結(jié)合，以避免快速排序在小數(shù)組上的性能下降。
pdqsort還使用了一些模式避免技術(shù)，以減少分支預(yù)測錯(cuò)誤和緩存行不命中的次數(shù)。這些優(yōu)化使得pdqsort在各種情況下都表現(xiàn)良好，尤其是對于大型、隨機(jī)分布的數(shù)據(jù)集。
pdqsort已經(jīng)被廣泛應(yīng)用于各種編程語言和庫中，如Go1.19 Rust、C++等。
復(fù)雜度
最好的情況：O(n)
平均情況：O(n*logn)
最壞的情況：O(n*logn)
pdqsort的不同版本
第一個(gè)版本
應(yīng)對短序列時(shí)，算法會(huì)使用插入排序，中序列或長序列則使用快速排序；
如果快速排序效果表現(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)于序列長度的函數(shù)）選取的 pivot 在本輪結(jié)束后的位置離數(shù)組兩端距離小于 n/8n/8 時(shí)，即判定快速排序效果表現(xiàn)不好。
總結(jié)：結(jié)合插入排序、快速排序和堆排序三種排序優(yōu)勢。
第二個(gè)版本
在第一個(gè)版本中，由于快速排序的速度制約著pdqsort的整體排序效率。
第二個(gè)版本主要優(yōu)化快速排序，具體是優(yōu)化快速排序中的選取基數(shù)pivot的代碼。
關(guān)于pivot的選擇
使用首個(gè)元素作為 pivot：業(yè)務(wù)簡單，但往往表現(xiàn)不佳，特別是在數(shù)組有序的情況。
遍歷數(shù)組，尋找數(shù)組中位數(shù)：遍歷迭代的代價(jià)高，綜合表現(xiàn)得性能不好，盡管能帶來很不錯(cuò)的效果。
平衡尋找 pivot 所需要的開銷及 pivot 帶來的性能優(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)檢測到此時(shí)的 pivot 和上次相同時(shí)(發(fā)生在 leftSubArray)，即partition進(jìn)行了無效分割，此時(shí)認(rèn)為pivot的值為重復(fù)元素，使用 partitionEqual 將重復(fù)元素排列在一起，減少重復(fù)元素對于 pivot 選擇的干擾
當(dāng) pivot 選擇策略表現(xiàn)不佳時(shí)，隨機(jī)交換元素
避免一些極端情況使得 QuickSort 總是表現(xiàn)不佳，以及一些黑客攻擊情況
pdqsort是一種新的排序算法，專為Go語言而設(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)過了精心的打造，旨在提供高效且穩(wěn)定的排序算法。對于Go語言的開發(fā)者來說，pdqsort是一個(gè)非常有價(jià)值的選擇。它不僅可以提高排序的效率，還可以減少開發(fā)者的工作量。因此，pdqsort是Go語言新寵，值得開發(fā)者們?nèi)L試和使用。
到此這篇關(guān)于Go語言新寵：pdqsort排序算法的完美打造的文章就介紹到這了,更多相關(guān)打造Go語言的pdqsort排序算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
go HTTP2 的頭部壓縮算法hpack實(shí)現(xiàn)詳解
這篇文章主要為大家介紹了go HTTP2 的頭部壓縮算法hpack實(shí)現(xiàn)詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-10-10
這篇文章主要介紹了在Go語言中使用JSON的相關(guān)資料,需要的朋友可以參考下2018-02-02
本文主要介紹了GO 切片刪除元素,根據(jù)要?jiǎng)h除元素的位置有三種情況,分別是從開頭位置刪除、從中間位置刪除和從尾部刪除,具有一定的參考價(jià)值,感興趣的可以了解一下2024-08-08
Goland調(diào)節(jié)字體大小的設(shè)置(編輯區(qū),terminal區(qū),頁面字體)
這篇文章主要介紹了Goland調(diào)節(jié)字體大小的設(shè)置(編輯區(qū),terminal區(qū),頁面字體)，具有很好的參考價(jià)值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-12-12
深入分析Go?實(shí)現(xiàn)?MySQL?數(shù)據(jù)庫事務(wù)
本文深入分析了Go語言實(shí)現(xiàn)MySQL數(shù)據(jù)庫事務(wù)的原理和實(shí)現(xiàn)方式，包括事務(wù)的ACID特性、事務(wù)的隔離級(jí)別、事務(wù)的實(shí)現(xiàn)方式等。同時(shí)，本文還介紹了Go語言中的事務(wù)處理機(jī)制和相關(guān)的API函數(shù)，以及如何使用Go語言實(shí)現(xiàn)MySQL數(shù)據(jù)庫事務(wù)。2023-06-06
Go?Excelize?API源碼解析GetSheetFormatPr使用示例
這篇文章主要為大家介紹了Go?Excelize?API源碼解析GetSheetFormatPr使用示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-08-08
Linux中Go環(huán)境配置和GoModule常用操作
這篇文章主要介紹了Linux中Go環(huán)境配置和GoModule,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2022-01-01
這篇文章主要介紹了GO語言獲取系統(tǒng)環(huán)境變量的方法,實(shí)例分析了Getenv方法操作環(huán)境變量的技巧,具有一定參考借鑒價(jià)值,需要的朋友可以參考下2015-02-02
Go語言基礎(chǔ)函數(shù)包的使用學(xué)習(xí)
本文通過一個(gè)實(shí)現(xiàn)加減乘除運(yùn)算的小程序來介紹go函數(shù)的使用，以及使用函數(shù)的注意事項(xiàng)，并引出了對包的了解和使用，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2023-05-05
gorm 結(jié)構(gòu)體中 binding 和 msg 結(jié)構(gòu)體標(biāo)簽示例詳解
文章介紹了Gin框架中binding和msg結(jié)構(gòu)體標(biāo)簽的使用,包括基本用法、常用驗(yàn)證規(guī)則、自定義驗(yàn)證器、錯(cuò)誤信息自定義、控制器使用示例、組合驗(yàn)證規(guī)則、跨字段驗(yàn)證和初始化驗(yàn)證器等,這些標(biāo)簽主要用于數(shù)據(jù)驗(yàn)證、自定義錯(cuò)誤信息、參數(shù)綁定和表單驗(yàn)證2024-11-11