? ? ? ?我一般是不會去主動(dòng)碰算法問題的。上學(xué)的時(shí)候一個(gè)算法復(fù)雜度就把我搞煩了，還想讓我去搞算法本身？我是這么安慰自己的：反正寫CRUD又不需要算法，這輩子都不需要算法的。好吧，其實(shí)我是一直不肯承認(rèn)，不去動(dòng)算法的原因只有三個(gè)字：因?yàn)楸浚?/p>
? ? ? ?所以你去看，一般招算法工程師的都是大廠，而且，薪水永遠(yuǎn)穩(wěn)居程序員工資的頂端位置。流傳在開發(fā)界的鄙視鏈中，算法工程師一直穩(wěn)居金字塔頂端，俯睨眾生。
? ? ? ?故，當(dāng)學(xué)員之中出現(xiàn)第一篇涉足算法，還寫的有模有樣的的博客的時(shí)候，我是有點(diǎn)吃驚的。雖然只是基礎(chǔ)算法，但這篇博客中除了涉及到了算法本身，還涉及到了源碼分析，同時(shí)為了保證論證的完整性，文末還給出了reference。
? ? ? ?這幾乎是一個(gè)優(yōu)秀程序員都會具備的素質(zhì)，可是我們的這位學(xué)員才學(xué)習(xí)了Java一個(gè)月啊~~。直到我看到學(xué)員本尊的時(shí)候，一切都釋然了。你們來感受下他的頭像，我可以保證確實(shí)是本尊無疑：
? ? ? ?隱藏的大俠都應(yīng)該是如此的。
? ? ? ?來，現(xiàn)在我們就來欣賞這位同學(xué)的博文，師徒班常同學(xué)的《Java中雙基準(zhǔn)快速排序方法(DualPivotQuicksort.sort())的具體實(shí)現(xiàn)》：
===========================================================
在Java語言的Arrays類下提供了一系列排序(sort)方法,幫助使用者對各種不同數(shù)據(jù)類型的數(shù)組進(jìn)行排序. 在1.7之后的版本中, Arrays.sort()方法在操作過程中實(shí)際調(diào)用的是DualPivotQuicksort類下的sort方法,DualPivotQuicksort和Arrays一樣,都在java.util包下,按字面翻譯過來,就是雙(Dual)基準(zhǔn)(Pivot)快速排序(Quicksort)算法.
雙基準(zhǔn)快速排序算法于2009年由Vladimir Yaroslavskiy提出,是對經(jīng)典快速排序(Classic Quicksort)進(jìn)行優(yōu)化后的一個(gè)版本, Java自1.7開始,均使用此方法作為默認(rèn)排序算法. 接下來,本文就將對此方法的具體實(shí)現(xiàn)過程進(jìn)行簡單的介紹.
在正式進(jìn)入對DualPivotQuicksort的介紹之前,我們先來對經(jīng)典快速排序的實(shí)現(xiàn)思路進(jìn)行一下簡單的了解:
經(jīng)典快速排序在操作過程中首先會從數(shù)組中選取一個(gè)基準(zhǔn)(Pivot),這個(gè)基準(zhǔn)可以是數(shù)組中的任意一個(gè)元素;
隨后,將這個(gè)數(shù)組所有其他元素和Pivot進(jìn)行比較,比Pivot小的數(shù)放在左側(cè),大的數(shù)放在右側(cè);
如此,我們就在Pivot的左側(cè)和右側(cè)各得到了一個(gè)新的數(shù)組;
接下來我們再在這兩個(gè)新的數(shù)組中各自選取新的Pivot,把小的放在左側(cè),大的放在右側(cè),循環(huán)往復(fù),最終就會得到由小到大順序排列的數(shù)組.
下圖(via wiki)便是Quicksort的一個(gè)具體實(shí)現(xiàn):
在對Quicksort的基本思路有了一定了解之后,下一步我們就來看Java中DualPivotQuicksort.sort是如何實(shí)現(xiàn)的;
本方法在實(shí)際工作過程中, 并不是對任何傳入的數(shù)組都直接進(jìn)行快速排序, 而是會先對數(shù)組進(jìn)行一系列測試, 然后根據(jù)數(shù)組的具體情況選擇最適合的算法來進(jìn)行排序,下面我們結(jié)合源碼來看:
首先, 以一個(gè)int數(shù)組為例,
當(dāng)一個(gè)數(shù)組int[] a被傳入DualPivotQuicksort.sort()時(shí),該方法還會要求其他一系列參數(shù):
static void sort(int[] a, int left, int right, int[] work, int workBase, int workLen)
其中,int[] a是需被排序的int數(shù)組, left和right是該數(shù)組中需要被排序的部分的左右界限. 而后面的work, workBase和workLen三個(gè)參數(shù)其實(shí)并不會參與雙基準(zhǔn)快速排序, 而是當(dāng)系統(tǒng)認(rèn)為本數(shù)組更適合使用歸并排序(merge sort)的時(shí)候, 供歸并排序使用.
但是,在實(shí)際使用中,我們并不希望為了排序設(shè)置這么多的參數(shù),因此:
Arrays.sort()在調(diào)用DualPivotQuicksort.sort()之前,對int數(shù)組的排序提供了兩種參數(shù)列表:
public static void sort(int[] a)
直接對int[] a 進(jìn)行排序,以及:
public static void sort(int[] a, int fromIndex, int toIndex)
對int[] a 中從fromIndex到toIndex(包頭不包尾)之間的元素進(jìn)行排序.
在這里,Arrays.sort()會自動(dòng)將int[] work, int workBase, int workLen設(shè)置為null,0,0 省去了使用者的麻煩.
緊接著,DualPivotQuicksort.sort()會對傳入的int數(shù)組進(jìn)行檢測, 具體流程如下:
這里先貼上整個(gè)方法的完整源碼, 然后按上圖中的流程逐步分析, 只想看DualPivotQuicksort的話可以直接跳到下面第7點(diǎn):
1. 判斷數(shù)組int[] a的長度是否大于常量QUICKSORT_THRESHOLD, 即286:
286是java設(shè)定的一個(gè)閾值,當(dāng)數(shù)組長度小于此值時(shí), 系統(tǒng)將不再考慮merge sort, 直接將參數(shù)傳入本類中的另一個(gè)私有sort方法進(jìn)行排序
2. 繼續(xù)判斷int[] a的長度是否大于常量INSERTION_SORT_THRESHOLD, 即47:
3. 若數(shù)組長度小于47, 則使用insertion sort:
數(shù)組傳入本類私有的sort方法后, 會繼續(xù)判斷數(shù)組長度是否大于47, 若小于此值, 則直接使用insertion sort并返回結(jié)果, 因?yàn)椴迦胨惴ú⒎潜疚闹攸c(diǎn), 此處不再展開敘述
值得注意的是, java在這里提供了兩種不同的插入排序算法, 當(dāng)傳入的參數(shù)leftmost真假值不同時(shí), 會使用不同的算法.
leftmost代表的是本次傳入的數(shù)組是否是從最初的int[] a的最左側(cè)left開始的, 因?yàn)楸痉椒ㄔ谡麄€(gè)排序過程中可能會針對數(shù)組的不同部分被多次調(diào)用, 因此leftmost有可能為false.
Quicksort的情況我們放到最后再談, 這里先回過來看第一步判斷中數(shù)組長度大于286的情形, 這種情況下, 系統(tǒng)會
4.繼續(xù)判斷該數(shù)組是否已經(jīng)高度結(jié)構(gòu)化(即已經(jīng)接近排序完成):
這里的基本思路是這樣的:
a. 定義一個(gè)常量MAX_RUN_COUNT = 67;
b. 定義一個(gè)計(jì)數(shù)器int count = 0; 定義一個(gè)數(shù)組int[] run 使之長度為MAX_RUN_COUNT + 1;
c. 令run[0] = left, 然后從傳入數(shù)組的最左側(cè)left開始遍歷, 若數(shù)組的前n個(gè)元素均為升序/降序排列, 而第n + 1個(gè)元素的升/降序發(fā)生了改變, 則將第n個(gè)元素的索引存入run[1], 同時(shí)++count, 此時(shí)count的值為1;
d. 從n + 1開始繼續(xù)遍歷, 直至升/降序再次改變, 再將此處的索引存入run[2], ++count, 此時(shí)count的值為2, 以此類推...
......
e. 若將整個(gè)數(shù)組全部遍歷完成后, count仍然小于MAX_RUN_COUNT (即整個(gè)數(shù)組升降序改變的次數(shù)低于67次), 證明該數(shù)組是高度結(jié)構(gòu)化的, 則使用merge sort進(jìn)行排序;
若count == MAX_RUN_COUNT時(shí), 還未完成對數(shù)組的遍歷, 則證明數(shù)組并非高度結(jié)構(gòu)化, 則調(diào)用前文所述私有sort方法進(jìn)行quicksort.
5. 判斷該數(shù)組是否是是已經(jīng)排列好的:
若該數(shù)組是高度結(jié)構(gòu)化的, 在使用merge sort進(jìn)行排序之前, 會先檢驗(yàn)數(shù)組是否本身就是排序好的, 思路很簡單, 如果在前面的檢測中一次就完成了遍歷, 就證明該數(shù)組是排序好的, 則直接返回結(jié)果:
?
*當(dāng)然, 在具體實(shí)現(xiàn)中還有不少其他要考慮的因素, 有興趣了解的話可以結(jié)合上一部分代碼進(jìn)行閱讀.
6. 進(jìn)行歸并排序(merge sort):
此處不再展開敘述, 值得注意的是, 由于歸并算法在操作過程中需要使用一塊額外的存儲空間, 本方法參數(shù)列表中要求的work, workBase和workLen三個(gè)參數(shù)就是在此處使用的:
?
7. 進(jìn)行雙基準(zhǔn)快速排序(dual pivot quicksort):
只有在上述情況都不滿足的情況下, 本方法才會使用雙基準(zhǔn)快速排序算法進(jìn)行排序,
算法本身的思路并不復(fù)雜, 和經(jīng)典快速排序相差不大, 顧名思義, 比起經(jīng)典快排, 該算法選取了兩個(gè)Pivot, 我們姑且稱之為P1和P2.
P1和P2都從數(shù)組中選出, P1在P2的右側(cè), 且P1必須小于P2, 如果不是, 則交換P1和P2的值;
接下來令數(shù)組中的每一個(gè)元素和基準(zhǔn)進(jìn)行比較, 比P1小的放在P1左邊, 比P2大的放在P2右邊, 介于兩者之間的放在中間.
這樣, 最終我們會的得到三個(gè)數(shù)組, 比P1小元素構(gòu)成的數(shù)組, 介于P1和P2之間的元素構(gòu)成的數(shù)組, 以及比P2大的元素構(gòu)成的數(shù)組.
最后, 遞歸地對這三個(gè)數(shù)組進(jìn)行排序, 最終得到排序完成的結(jié)果.
思路上雖然, 并不復(fù)雜, 但Java為了盡可能的提高效率, 在對這個(gè)算法進(jìn)行實(shí)現(xiàn)的過程中增加了非常多的細(xì)節(jié), 下面我們就來大致看一下其中的部分內(nèi)容:
?
先貼上這部分完整的代碼
首先, 也是本方法中最具特色的部分, 就是對Pivot的選取:
在這里, 系統(tǒng)會先通過位運(yùn)算獲取數(shù)組長度的1/7的近似值(位運(yùn)算無法精確表示1/7)
int seventh = (length >> 3) + (length >> 6) + 1;
然后獲取本數(shù)組中間位置的索引e3:
int e3 = (left + right) >>> 1; // The midpoint
在中間位置的左右1/7, 2/7處各獲取兩個(gè)索引(e1, e2, e4, e5):
int e2 = e3 - seventh;
int e1 = e2 - seventh;
int e4 = e3 + seventh;
int e5 = e4 + seventh;
將這五個(gè)索引對應(yīng)的值用插入算法進(jìn)行有小到大的排序后, 再放回五個(gè)索引的位置
對索引的值排序
接下來進(jìn)行判斷, 若這五個(gè)索引對應(yīng)的元素值各不相同, 則選取e2的值作為Pivot1, e4的值作為Pivot2(特別注意基準(zhǔn)是值而不是元素), 然后進(jìn)行雙基準(zhǔn)快排, Java聲稱這種選法比其他方式更加高效;
但如果這五個(gè)值中有相同的存在, 則本輪排序選取e3的值作為Pivot, 進(jìn)行單基準(zhǔn)快排, 同樣, Java聲稱這種選取方式要比隨機(jī)選取更加高效.
至于具體排序的部分, 其實(shí)并沒有太多可以敘述的內(nèi)容, 值得注意的是, 由于在遞歸的過程中會不斷地調(diào)用私有的sort方法, 所以在遞歸中獲得的子數(shù)組長度小47時(shí), 會改為調(diào)用插入排序.
此外, 源碼中還有一些可以借鑒的用來提高效率的小竅門, 比如在對元素進(jìn)行交換位置之前先過濾掉頭尾處已經(jīng)在正確位置的元素等, 有興趣的話可以再對源碼進(jìn)行仔細(xì)閱讀.
至此, 關(guān)于DualPivotQuicksort.sort()的大致實(shí)現(xiàn)過程的介紹也就基本結(jié)束了, 最后我們不妨進(jìn)行一個(gè)簡單的測試, 看看它是否真的比經(jīng)典快排更加高效:
首先, 我們先來測試一下經(jīng)典Quicksort的性能, 對包含一億個(gè)Random.nextInt()隨機(jī)數(shù)的數(shù)組進(jìn)行排序, 重復(fù)十次求平均排序運(yùn)行時(shí)間,
具體代碼如下, 其中經(jīng)典快排的代碼摘自wiki快速排序條目:
經(jīng)典快排測試
經(jīng)過測試, 我們得到結(jié)果, 十次排序的運(yùn)行時(shí)間分別為2405 3017 3021 2972 2993 2967 2992 2954 3001 2984(ms),
平均時(shí)間則是2930ms
接下來, 再對DualPivotQuicksort.sort()使用同樣的方法進(jìn)行測試, 直接用Arrays.sort()進(jìn)行排序,代碼如下:
雙基準(zhǔn)快排測試
十次運(yùn)行時(shí)間分別是115 16 31 21 28 118 62 78 78 63(ms).
平均時(shí)間則達(dá)到了驚人的61ms.
當(dāng)然, 之所以會產(chǎn)生如此巨大的差距, 一方面是因?yàn)殡p基準(zhǔn)快排本身性能更加優(yōu)秀, 另一方也是因?yàn)镴ava對該方法進(jìn)行了大量的優(yōu)化, 而選取測試的經(jīng)典快排則相當(dāng)粗糙, 只是這種算法思想的體現(xiàn), 并不是說兩種算法本身性能上存在著這種程度的差距.
Reference:
Quicksort - wiki
https://en.wikipedia.org/wiki/Quicksort
快速排序?- wiki
https://zh.wikipedia.org/zh-cn/%E5%BF%AB%E9%80%9F%E6%8E%92%E5%BA%8F
java.util.Arrays
java.util.DualPivotQuicksort
再一次的分割線
===========================================================
1：常同學(xué)的原文博客在：http://www.cnblogs.com/chang4/
2：師徒班持續(xù)招生中，想成為像劉同學(xué)一樣的優(yōu)秀學(xué)員，請來這里報(bào)名：http://www.zuikc.com
