數(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ù)的元素都交換到中間后,對兩端不等的元素使用快排,左側(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算法里判斷。
|
|
傳智Java培訓(xùn)擁有6大課程優(yōu)勢:
?、侏?dú)有的一站式IT職業(yè)教育體系,讓學(xué)員通過6個(gè)月的線下學(xué)習(xí)實(shí)現(xiàn)高起點(diǎn)就業(yè), 12個(gè)月的線上在職進(jìn)階課實(shí)現(xiàn)升職加薪,大幅提升學(xué)員的職場晉升速度。
?、?0+套技術(shù)解決方案,覆蓋職場常見開發(fā)問題,讓學(xué)員就業(yè)后快速上手開發(fā)難題,輕松成為核心員工。
③超大項(xiàng)目庫,覆蓋7大就業(yè)主流熱門行業(yè),讓學(xué)員邊學(xué)習(xí)邊積累項(xiàng)目開發(fā)經(jīng)驗(yàn)。
④超千人投入的3大課程研發(fā)庫,每年耗資千萬打造領(lǐng)先行業(yè)的優(yōu)質(zhì)課程。
⑤傳智&華為課程共建,持續(xù)為課程輸出前沿技術(shù)。
⑥120+超強(qiáng)師資團(tuán)隊(duì),多為總監(jiān)、架構(gòu)師出身,除了專業(yè)技能,還為你規(guī)劃適合你的職業(yè)發(fā)展路線。