java培訓(xùn):Arrays.sort()的內(nèi)部排序機(jī)制

　　數(shù)組的操作可以使用java提供的工具類Arrays，其中Arrays.sort()方法用于數(shù)組的排序。
　　基本數(shù)據(jù)類型數(shù)組的操作，使用經(jīng)過優(yōu)化的快速排序算法
　　當(dāng)數(shù)組的規(guī)模較小時(shí)，直接插入排序的比較次數(shù)并不會(huì)比快排或者歸并多多少，其效率反而不如簡單排序算法，所以在數(shù)組規(guī)模小于7時(shí)，使用直接插入排序，
　　當(dāng)數(shù)組規(guī)模較大時(shí)，合理的選擇快排的樞軸元素，如在規(guī)模小于40時(shí)，在數(shù)組的首，中，尾三個(gè)位置上的數(shù)，取中間大小的數(shù)做樞軸;在數(shù)組規(guī)模大于40時(shí)，從數(shù)組中取位置均勻分布的9個(gè)數(shù)，然后每三個(gè)數(shù)一組取中間數(shù)，最后三個(gè)中間數(shù)再取中間數(shù)。確定樞軸后，與數(shù)組的第一個(gè)元素交換，之后的快排與普通快排一樣。
　　當(dāng)數(shù)組中有大量重復(fù)元素時(shí)，選擇重復(fù)元素作為樞軸，然后兩個(gè)端各設(shè)置兩個(gè)工作指針low、high，left、right用于始終指向要交換的元素位置，如5，2，5，6，4，3，5，1，5，7
　　從high開始判斷，low <= high，若high位置的元素 >= 基準(zhǔn)元素high–，同時(shí)若high位置的元素 == 基準(zhǔn)元素，high位置的元素與right位置的元素交換，同時(shí)right–，繼續(xù)直到high位置的元素 < 基準(zhǔn)元素。
　　從low開始判斷，low <= high，若low位置的元素 <= 基準(zhǔn)元素low++，同時(shí)若low位置的元素 = 基準(zhǔn)元素，low位置的元素與left位置的元素交換，同時(shí)left++，繼續(xù)直到low位置的元素 > 基準(zhǔn)元素。
　　low、high位置的元素交換，同時(shí)low++、high–，然后再從high開始繼續(xù)上面的過程，最后將重復(fù)的元素至于序列的兩端，中間的序列分成了兩部分，左面的為小于基準(zhǔn)元素的，右面的為大于基準(zhǔn)元素的，如5，5，2，1，4，3，7，6，5，5，此時(shí)low在7位置，high在3位置。
　　將兩端重復(fù)的元素都交換到中間后，對(duì)兩端不等的元素使用快排，左側(cè)外循環(huán)從下標(biāo)0開始判斷，若等于樞軸進(jìn)入內(nèi)循環(huán)，內(nèi)循環(huán)從下標(biāo)low - 1開始向前找不等于樞軸的，找到交換，直到外循環(huán)遇到不等于樞軸的退出;右側(cè)外循環(huán)從下標(biāo)n - 1開始判斷，若等于樞軸進(jìn)入內(nèi)循環(huán)，內(nèi)循環(huán)從下標(biāo)high + 1開始向后找不等于樞軸的，找到交換，直到外循環(huán)遇到不等于樞軸的退出。
　　引用數(shù)據(jù)類型數(shù)組的排序，使用經(jīng)過優(yōu)化的歸并排序算法。
　　當(dāng)數(shù)組規(guī)模j較小時(shí)，使用直接插入排序。
　　當(dāng)屬組規(guī)模較大時(shí)，使用歸并排序，且當(dāng)合并的兩個(gè)有序序列中，低子序列的最高元素小于高子序列的最低元素時(shí)，無序執(zhí)行合并算法，這個(gè)可以在merge算法里判斷。

全國校區(qū)

熱門課程

java培訓(xùn):Arrays.sort()的內(nèi)部排序機(jī)制

最新資訊

相關(guān)閱讀

熱門課程推薦