各種排序算法及其java程序?qū)崿F(xiàn)

1、各種排序算法及其java程序?qū)崿F(xiàn)問題：各種排序算法及其java程序?qū)崿F(xiàn)回答：各種排序算法：冒擇路（入）兮（?。┛鞖w堆，桶式排序，基數(shù)排序冒泡排序，選擇排序，插入排序，稀爾排序，快速排序，歸并排序，堆排序，桶式排序，基數(shù)排序一、冒泡排序（BubbleSort）.基本思想：兩兩比較待排序數(shù)據(jù)元素的大小，發(fā)現(xiàn)兩個數(shù)據(jù)元素的次序相反時即進行交換，直到?jīng)]有反序的數(shù)據(jù)元素為止。.排序過程：設(shè)想被排序的數(shù)組R1.N垂直豎立，將每個數(shù)據(jù)元素看作有重量的氣泡，根據(jù)輕氣泡不能在重氣泡之下的原則，從下往上掃描數(shù)組R,凡掃描到違反本原則的輕氣泡，就使其向上漂浮，如此反復(fù)進行，直至最后任何兩個氣泡都是輕者在上，重者在下

2、為止。【示例】：49131313131313133849272727272727653849383838383897653849494949497697654949494949137697656565656527277697767676764949497697979797java代碼實現(xiàn)：/*02.*冒泡排序：執(zhí)行完一次內(nèi)for循環(huán)后，最小的一個數(shù)放到了數(shù)組的最前面(跟那一個排序算法*不一樣)。相鄰位置之間交換03.*/04.05.publicclassBubbleSort06.07./*08.*排序算法的實現(xiàn)，對數(shù)組中指定的元素進行排序09.*paramarray待排序的數(shù)組*paramfr

3、om從哪里開始排序*paramend排到哪里*paramc比較器*/publicvoidbubble(Integer口array,intfrom,intend)/需array.length1輪比較for(intk=1;k/每輪循環(huán)中從最后一個元素開始向前起泡，直到i=k止,即i等于輪次止for(inti=endfrom;i=k;i)/按照一種規(guī)則(后面元素不能小于前面元素)排序if(pareTo(arrayi-1)/如果后面元素小于了(當(dāng)然是大于還是小于要看比較器實現(xiàn)了)前面的元素，則前后交換swap(array,i,i1);/*交換數(shù)組中的兩個元素的位置*paramarray待交換的數(shù)組*p

4、arami第一個元素*paramj第二個元素*/publicvoidswap(Integer口array,inti,intj)if(i!=j)/只有不是同一位置時才需交換Integertmp=arrayi;arrayi=arrayj;arrayj=tmp;/*測試*paramargs*/publicstaticvoidmain(String口args)Integer口intgArr=7,2,4,3,12,1,9,6,8,5,11,10;BubbleSortbubblesort=newBubbleSort();bubblesort.bubble(intgArr,0,intgArr.length-

5、1);for(IntegerintObj:intgArr)System.out.print(intObj+);另外一種實現(xiàn)方式：/*冒泡排序：執(zhí)行完一次內(nèi)for循環(huán)后，最大的一個數(shù)放到了數(shù)組的最后面。相鄰位置之間交換*/publicclassBubbleSort2publicstaticvoidmain(String口args)int口a=3,5,9,4,7,8,6,1,2;BubbleSort2bubble=newBubbleSort2();bubble.bubble(a);for(intnum:a)System.out.print(num+);publicvoidbubble(int口a)

6、for(inti=a.length-1;i0;i)j+1)0)for(intj=0;jif(newInteger(aj).compareTo(newInteger(aswap(a,j,j+1);publicvoidswap(int口a,intx,inty)inttemp;temp=ax;ax=ay；ay=temp;二、選擇排序.基本思想：每一趟從待排序的數(shù)據(jù)元素中選出最?。ɑ蜃畲螅┑囊粋€元素,順序放在已排好序的數(shù)列的最后，直到全部待排序的數(shù)據(jù)元素排完。2.排序過程：【示例】：初始關(guān)鍵字4938659776132749第一趟排序后1338659776492749第二趟排序/p>

7、93849第三趟排序后1327389776496549第四趟排序后1327384949976576第五趟排序后1327384949979776第六趟排序后1327384949767697第七趟排序后1327384949767697最后排序結(jié)果1327384949767697java代碼實現(xiàn)：01./*02.*簡單選擇排序：執(zhí)行完一次內(nèi)for循環(huán)后最小的一個數(shù)放在了數(shù)組的最前面。03.*/04.publicclassSelectSort05.06./*07.*排序算法的實現(xiàn)，對數(shù)組中指定的元素進行排序08.*paramarray待排序的數(shù)組09.*paramfrom從哪里開始排序*paramen

8、d排到哪里*paramc比較器*/publicvoidselect(Integer口array)intminIndex;/最小索引/*循環(huán)整個數(shù)組(其實這里的上界為array.length1即可,因為當(dāng)i=array.length-1*時，最后一個元素就已是最大的了，如果為array.length時，內(nèi)層循環(huán)將不再循環(huán))，每輪假設(shè)*第一個元素為最小元素，如果從第一元素后能選出比第一個元素更小元素，則讓讓最小元素與第一*個元素交換*/for(inti=0;iminIndex=i;/假設(shè)每輪第一個元素為最小元素從假設(shè)的最小元素的下一元素開始循環(huán)for(intj=i+1;j如果發(fā)現(xiàn)有比當(dāng)前array

9、smallIndex更小元素，則記下該元素的索引于smallIndex中if(pareTo(arrayminIndex)minIndex=j;先前只是記錄最小元素索引，當(dāng)最小元素索引確定后，再與每輪的第一個元素交換swap(array,i,minIndex);publicstaticvoidswap(Integer口intgArr,intx,inty)/Integertemp;/這個也行inttemp;temp=intgAr僅;intgArrx=intgArry;intgArry=temp;/*測試*paramargs*/publicstaticvoidmain(String口args)Int

10、eger口intgArr=5,9,1,4,2,6,3,8,0,7;SelectSortinsertSort=newSelectSort();insertSort.select(intgArr);for(IntegerintObj:intgArr)System.out.print(intObj+);三、插入排序(InsertionSort).基本思想：每次將一個待排序的數(shù)據(jù)元素，插入到前面已經(jīng)排好序的數(shù)列中的適當(dāng)位置，使數(shù)列依然有序；直到待排序數(shù)據(jù)元素全部插入完為止。.排序過程:初始關(guān)鍵字4938659776132749J=2(38)3849659776132749J=3(65)38496597

11、76132749J=4(97)3849659776132749J=5(76)3849657697132749J=6(13)1338496576972749J=7(27)1327384965769749J=8(49)1327384949657697java代碼實現(xiàn):/*直接插入排序:注意所有排序都是從小到大排。*/publicclassInsertSort/*排序算法的實現(xiàn)，對數(shù)組中指定的元素進行排序* param array待排序的數(shù)組* param from從哪里開始排序paramend排到哪里*paramc比較器/publicvoidinsert(Integer口array,intfrom

12、,intend)/*第一層循環(huán)：對待插入(排序)的元素進行循環(huán)從待排序數(shù)組斷的第二個元素開始循環(huán)，到最后一個元素(包括)止/for(inti=from+1;i/*第二層循環(huán)：對有序數(shù)組進行循環(huán)，且從有序數(shù)組最第一個元素開始向后循環(huán)找到第一個大于待插入的元素有序數(shù)組初始元素只有一個，且為源數(shù)組的第一個元素，一個元素數(shù)組總是有序的/for(intj=0;jIntegerinsertedElem=arrayi;待插入到有序數(shù)組的元素/從有序數(shù)組中最一個元素開始查找第一個大于待插入的元素if(pareTo(insertedElem)0)找到插入點后，從插入點開始向后所有元素后移一位move(array

13、,j,i1);/將待排序元素插入到有序數(shù)組中arrayj=insertedElem;break;/=以下是java.util.Arrays的插入排序算法的實現(xiàn)/*該算法看起來比較簡潔一j點，有點像冒泡算法。將數(shù)組邏輯上分成前后兩個集合，前面的集合是已經(jīng)排序好序的元素，而后面集合為待排序的集合，每次內(nèi)層循從后面集合中拿出一個元素，通過冒泡的形式，從前面集合最后一個元素開始往前比較，如果發(fā)現(xiàn)前面元素大于后面元素，則交換，否則循環(huán)退出*總感覺這種算術(shù)有點怪怪，既然是插入排序，應(yīng)該是先找到插入點，而后再將待排序的元素插入到的插入點上，那么其他元素就必然向后移，感覺算法與排序名稱不匹，但返過來與上面實*

14、現(xiàn)比，其實是一樣的，只是上面先找插入點，待找到后一次性將大的元素向后移，而該算法卻*是走rH少，步一步將待排序元素往前移*/*for(inti=from;ifor(intj=i;jpare(arrayj-1,arrayj)0;j)swap(array,j,j1);*/*數(shù)組元素后移*paramarray待移動的數(shù)組*paramstartindex從哪個開始移*paramendindex到哪個元素止*/intpublicvoidmove(Integer口array,intstartindex,endindex)for(inti=endindex;i=startindex;i)arrayi+1=a

15、rrayi;*測試*paramargs*/publicstaticvoidmain(String口args)Integer口intgArr=5,9,1,4,2,6,3,8,0,7;InsertSortinsertSort=new2-1,2-1,2-1)04.*注意所有排序都是從小到大排。05.*/06.publicclassShellSort07.08./*09.*排序算法的實現(xiàn)，對數(shù)組中指定的元素進行排序*paramarray待排序的數(shù)組*paramfrom從哪里開始排序*paramend排到哪里*paramc比較器*/publicvoidsort(Integerarray,intfrom,

16、intend)/初始步長，實質(zhì)為每輪的分組數(shù)intstep=initialStep(endfrom+1);18.第一層循環(huán)是對排序輪次進行循環(huán)。(step+1)/21為下一輪步長值for(;step=1;step=(step+1)/21)/對每輪里的每個分組進行循環(huán)for(intgroupIndex=0;groupIndex/對每組進行直接插入排序insertSort(array,groupIndex,step,end);/*直接插入排序?qū)崿F(xiàn)*paramarray待排序數(shù)組*paramgroupIndex對每輪的哪一組進行排序*paramstep步長*paramend整個數(shù)組要排哪個元素止*p

17、aramc比較器*/publicvoidinsertSort(Integerarray,intgroupIndex,intstep,intend)intstartindex=groupIndex;/從哪里開始排序intendindex=startindex;/排至U哪里/*排到哪里需要計算得到，從開始排序元素開始，以step步長，可求得下元素是否在數(shù)組范圍內(nèi)，*如果在數(shù)組范圍內(nèi)，則繼續(xù)循環(huán)，直到索引超現(xiàn)數(shù)組范圍*/while(endindex+step)endindex+=step;/i為每小組里的第二個元素開始for(inti=groupindex+step;ifor(intj=groupi

18、ndex;jintegerinsertedElem=arrayi;/從有序數(shù)組中最一個元素開始查找第一個大于待插入的元素if(pareTo(insertedElem)=0)/找到插入點后，從插入點開始向后所有元素后移一位move(array,j,istep,step);arrayj=insertedElem;break;p+1)*21step=(step+1)*21;System.out.println(初始步長：+step);returnstep;/*以指定的步長將數(shù)組元素后移，步長指定每個元素間的間隔*paramarray待排序數(shù)組*paramstartIndex從哪里開始移*parame

19、ndIndex到哪個元素止*paramstep步長*/protectedfinalvoidmove(Integer口array,intstartIndex,intendIndex,intstep)for(inti=endIndex;i=startIndex;i-=step)arrayi+step=arrayi;/*測試*paramargs*/publicstaticvoidmain(String口args)Integer口intgArr=5,9,1,4,8,2,6,3,7,0;ShellSortshellSort=newShellSort();shellSort.sort(intgArr,0,

20、intgArr.length-1);for(IntegerintObj:intgArr)System.out.print(intObj+);五、快速排序(QuickSort).基本思想：在當(dāng)前無序區(qū)R1.H中任取一個數(shù)據(jù)元素作為比較的基準(zhǔn)(不妨記為X),用此基準(zhǔn)將當(dāng)前無序區(qū)劃分為左右兩個較小的無序區(qū)：R1.I-1和RI+1.H，且左邊的無序子區(qū)中數(shù)據(jù)元素均小于等于基準(zhǔn)元素，右邊的無序子區(qū)中數(shù)據(jù)元素均大于等于基準(zhǔn)元素，而基準(zhǔn)X則位于最終排序的位置上，即R1.I-1X.Keyhigth,則說明上次樞紐元素的位置pivot就是low或者是higth,此種情況*下分區(qū)不存，也不需處理*/if(low對

21、分區(qū)進行排序整理intpivot=partition1(array,low,high);intpivot=partition2(array,low,high);intpivot=partition3(array,low,high);/*以pivot為邊界，把數(shù)組分成三部分low,pivot-1、pivot、pivot+1,high*其中pivot為樞紐元素，不需處理，再對low,pivot-1與pivot+1,high*各自進行分區(qū)排序整理與進一步分區(qū)*/quickSort(array,low,pivot1);quickSort(array,pivot+1,high);47./*實現(xiàn)一*par

22、amarray待排序數(shù)組*paramlow低指針*paramhigh高指針*paramc比較器*returnint調(diào)整后中樞位置*/privateintpartition1(Integerarray,intlow,inthigh)IntegerpivotElem=arraylow;/以第一個元素為中樞元素/從前向后依次指向比中樞元素小的元素，剛開始時指向中樞，也是小于與大小中樞的元素的分界點intborder=low;/*在中樞元素后面的元素中查找小于中樞元素的所有元素，并依次從第二個位置從前往后存放*注，這里最好使用i來移動，如果直接移動low的話，最后不知道數(shù)組的邊界了，但后面需要*知道數(shù)

23、組的邊界*/for(inti=low+1;i如果找到一個比中樞元素小的元素if(pareTo(pivotElem)swap(array,+border,i);/border前移，表示有小于中樞元素的元素/*如果border沒有移動時說明說明后面的元素都比中樞元素要大，border與low相等，此時是*同一位置交換，是否交換都沒關(guān)系；當(dāng)border移到了high時說明所有元素都小于中樞元素，此*時將中樞元素與最后一個元素交換即可，即low與high進行交換，大的中樞元素移到了序列最*后；如果low*中樞元素，此時中樞元素與前部分數(shù)組中最后一個小于它的元素交換位置，使得中樞元素放置在*正確的位置*

24、/swap(array,border,low);returnborder;/*實現(xiàn)二*paramarray待排序數(shù)組*paramlow待排序區(qū)低指針*paramhigh待排序區(qū)高指針*paramc比較器*returnint調(diào)整后中樞位置*/privateintpartition2(Integerarray,intlow,inthigh)intpivot=low;/中樞元素位置，我們以第一個元素為中樞元素/退出條件這里只可能是low=highwhile(true)if(pivot!=high)/如果中樞元素在低指針位置時，我們移動高指針如果高指針元素小于中樞元素時，則與中樞元素交換if(pare

25、To(arraypivot)swap(array,high,pivot);交換后中樞元素在高指針位置了pivot=high;else/如果未找到小于中樞元素，則高指針前移繼續(xù)找highelse/否則中樞元素在高指針位置如果低指針元素大于中樞元素時，則與中樞元素交換if(pareTo(arraypivot)0)swap(array,low,pivot);/交換后中樞元素在低指針位置了pivot=low;else/如果未找到大于中樞元素，則低指針后移繼續(xù)找low+;if(low=high)break;/返回中樞元素所在位置，以便下次分區(qū)returnpivot;/*實現(xiàn)三*paramarray待排序

26、數(shù)組*paramlow待排序區(qū)低指針*paramhigh待排序區(qū)高指針*paramc比較器*returnint調(diào)整后中樞位置*/privateintpartition3(Integerarray,intlow,inthigh)intpivot=low;/中樞元素位置，我們以第一個元素為中樞元素low+;/-調(diào)整高低指針?biāo)赶虻脑仨樞?，把小于中樞元素的移到前部分，大于中樞元素的移到后面部?退出條件這里只可能是low=highwhile(true)如果高指針未超出低指針while(low如果低指針指向的元素大于或等于中樞元素時表示找到了，退出，注：等于時也要后移if(pareTo(arrayp

27、ivot)=0)break;else/如果低指針指向的元素小于中樞元素時繼續(xù)找low+;while(highlow)/如果高指針指向的元素小于中樞元素時表示找到，退出if(pareTo(arraypivot)break;else/如果高指針指向的元素大于中樞元素時繼續(xù)找high/退出上面循環(huán)時low=highif(low=high)break;164.swap(array,low,high);-高低指針?biāo)赶虻脑嘏判蛲瓿珊?，還得要把中樞元素放到適當(dāng)?shù)奈恢胕f(pareTo(arraylow)0)如果退出循環(huán)時中樞元素大于了低指針或高指針元素時,中樞元素需與low元素交換swap(array,

28、low,pivot);pivot=low;elseif(pareTo(arraylow)swap(array,low1,pivot);pivot=low1;/返回中樞元素所在位置，以便下次分區(qū)returnpivot;184. *交換數(shù)組中的兩個元素的位置*paramarray待交換的數(shù)組*parami第一個元素*paramj第二個元素*/publicvoidswap(Integer口array,inti,intj)if(i!=j)/只有不是同一位置時才需交換Integertmp=arrayi;arrayi=arrayj;arrayj=tmp;/*測試*paramargs*/publicstat

29、icvoidmain(Stringargs)Integer口intgArr=5,9,1,4,2,6,3,8,0,7;Quicksortquicksort=newQuickSort();quicksort.sort(intgArr,0,intgArr.length-1);for(IntegerintObj:intgArr)System.out.print(intObj+);207.208.209.六、歸并排序java代碼實現(xiàn)：*02.歸并排序：里面是一個遞歸程序，深刻理解之。03.*/04.publicclassMergeSort05.06./*07.*遞歸劃分數(shù)組08.*paramarr09.

30、*paramfrom*paramend*paramcvoid*/publicvoidpartition(Integerarr,intfrom,intend)/劃分到數(shù)組只有一個元素時才不進行再劃分if(from/從中間劃分成兩個數(shù)組intmid=(from+end)/2;partition(arr,from,mid);partition(arr,mid+1,end);/合并劃分后的兩個數(shù)組merge(arr,from,end,mid);/*數(shù)組合并，合并過程中對兩部分數(shù)組進行排序*前后兩部分數(shù)組里是有序的*paramarr*paramfrom*paramend*parammid*paramcv

31、oid*/publicvoidmerge(Integerarr,intfrom,intend,intmid)IntegertmpArr=newInteger10;36. int tmpArrIndex = 0;/指向臨時數(shù)組intpartlArrIndex=from;/指向第一部分數(shù)組intpart2ArrIndex=mid+1;指向第二部分數(shù)組由于兩部分數(shù)組里是有序的，所以每部分可以從第一個元素依次取到最后一個元素，再對兩部分/取出的元素進行比較。只要某部分數(shù)組元素取完后，退出循環(huán)while(part1ArrIndex/從兩部分數(shù)組里各取一個進行比較，取最小一個并放入臨時數(shù)組中if(arrp

32、art1ArrIndexarrpart2ArrIndex/如果第一部分數(shù)組元素小，則將第一部分數(shù)組元素放入臨時數(shù)組中，并且臨時數(shù)組指針/tmpArrIndex下移一個以做好下次存儲位置準(zhǔn)備，前部分數(shù)組指針part1ArrIndex/也要下移一個以便下次取出下一個元素與后部分數(shù)組元素比較tmpArrtmpArrIndex+=arrpart1ArrIndex+;else如果第二部分數(shù)組元素小，則將第二部分數(shù)組元素放入臨時數(shù)組中tmpArrtmpArrIndex+=arrpart2ArrIndex+;由于退出循環(huán)后，兩部分數(shù)組中可能有一個數(shù)組元素還未處理完，所以需要額外的處理，當(dāng)然不可/能兩部分數(shù)組

33、都有未處理完的元素，所以下面兩個循環(huán)最多只有一個會執(zhí)行，并且都是大于已放入臨時數(shù)組中的元素while(partlArrlndextmpArrtmpArrIndex+=arrpart1ArrIndex+;while(part2ArrIndextmpArrtmpArrIndex+=arrpart2ArrIndex+;/最后把臨時數(shù)組拷貝到源數(shù)組相同的位置System.arraycopy(tmpArr,0,arr,from,endfrom+1);/*測試*paramargs*/publicstaticvoidmain(String口args)Integer口intgArr=5,9,1,4,2,6,3

34、,8,0,7;MergeSortinsertSort=newMergeSort();insertSort.partition(intgArr,0,intgArr.length-1);for(Integera:intgArr)System.out.print(a+);七、堆排序(HeapSort).基本思想：堆排序是一樹形選擇排序，在排序過程中，將R1.N看成是一顆完全二叉樹的順序存儲結(jié)構(gòu)，利用完全二叉樹中雙親結(jié)點和孩子結(jié)點之間的內(nèi)在關(guān)系來選擇最小的元素。.堆的定義：N個元素的序列K1,K2K3,Kn.稱為堆，當(dāng)且僅當(dāng)該序列滿足特性：KiK2iKi=2;i)/根節(jié)點與最后一個葉子節(jié)點交換位置，即

35、數(shù)組中的第一個元素與最后一個元素互換swap(array,from,i1);/交換后需要重新調(diào)整堆adjustNote(array,1,i1);/*初始化堆比如原序列為：7,2,4,3,12,1,9,6,8,5,10,11*則初始堆為：1,2,4,3,5,7,9,6,8,12,10,11*paramarr排序數(shù)組*paramfrom從哪*paramend到哪*paramc比較器*/privatevoidinitialHeap(Integer口arr,intfrom,intend)intlastBranchIndex=(endfrom+1)/2;/最后一個非葉子節(jié)點/對所有的非葉子節(jié)點進行循環(huán)，

36、且從最一個非葉子節(jié)點開始for(inti=lastBranchIndex;i=1;i)adjustNote(arr,i,endfrom+1);/*調(diào)整節(jié)點順序，從父、左右子節(jié)點三個節(jié)點中選擇一個最大節(jié)點與父節(jié)點轉(zhuǎn)換*paramarr待排序數(shù)組*paramparentNodeIndex要調(diào)整的節(jié)點，與它的子節(jié)點一起進行調(diào)整*paramlen樹的節(jié)點數(shù)*paramc比較器*/privatevoidadjustNote(Integer口parentNodelndex,intlen)intminNodeIndex=parentNodeIndex;/如果有左子樹，i*2為左子節(jié)點索引if(parentN

37、odeIndex*2/如果父節(jié)點小于左子樹時if(arrparentNodeIpareTo(arrparentNodeIndex*2-1)minNodeIndex=parentNodeIndex*2;/為左子節(jié)點索引/只有在有或子樹的前提下才可能有右子樹，是否有右子樹if(parentNodeIndex*2+1/如果右子樹比最大節(jié)點更大if(arrminNodeIndexarr, int記錄最大索引再進一步斷判pareTo(arr(parentNodeIndex*2+1)-1)記錄最大minNodelndex=parentNodelndex*2+1;/索引為右子節(jié)點索引/如果在父節(jié)點、左、右子

38、節(jié)點三都中，最大節(jié)點不是父節(jié)點時需交換，把最大的與父節(jié)點交換，創(chuàng)建大頂堆if(minNodeIndex!=parentNodeIndex)swap(arr,parentNodeIndex1,minNodeIndex1);交換后可能需要重建堆，原父節(jié)點可能需要繼續(xù)下沉if(minNodeIndex*2adjustNote(arr,minNodeIndex,len);/*交換數(shù)組中的兩個元素的位置*paramarray待交換的數(shù)組*parami第一個元素*paramj第二個元素*/publicvoidswap(Integer口array,inti,intj)if(i!=j)/只有不是同一位置時才需

39、交換Integertmp=arrayi;arrayi=arrayj;arrayj=tmp;/*測試*paramargs*/publicstaticvoidmain(Stringargs)Integer口intgArr=5,9,1,4,2,6,3,8,0,7;HeapSortheapsort=newHeapSort();heapsort.sort(intgArr,0,intgArr.length-1);for(IntegerintObj:intgArr)System.out.print(intObj+);109.八、桶式排序java代碼實現(xiàn)：01./*02.*桶式排序：03.*桶式排序不再是基于

40、比較的了，它和基數(shù)排序同屬于分配類的排序，04.*這類排序的特點是事先要知道待排序列的一些特征。05.*桶式排序事先要知道待排序列在一個范圍內(nèi)，而且這個范圍應(yīng)該不是很大的。06.*比如知道待排序列在0,M)內(nèi)，那么可以分配M個桶，第I個桶記錄I的出現(xiàn)情況，07.*最后根據(jù)每個桶收到的位置信息把數(shù)據(jù)輸出成有序的形式。08.*這里我們用兩個臨時性數(shù)組，一個用于記錄位置信息，一個用于方便輸出數(shù)據(jù)成有序方式，09.*另外我們假設(shè)數(shù)據(jù)落在0到MAX,如果所給數(shù)據(jù)不是從0開始，你可以把每個數(shù)減去最小的數(shù)。*/publicclassBucketSortpublicvoidsort(intkeys,intfr

41、om,intlen,intmax)inttemp=newintlen;int口count=newintmax;for(inti=0;icountkeysfrom+i+;/calculatepositioninfofor(inti=1;icounti=counti+counti-1;這意味著有多少數(shù)目小于或等于i,因此它也是position+1System.arraycopy(keys,from,temp,0,len);for(intk=len-1;k=0;k)/從最末到開頭保持穩(wěn)定性keys-counttempk=tempk;position+1=count*paramargs*/public

42、staticvoidmain(String口args)int口a=1,4,8,3,2,9,5,0,7,6,9,10,9,13,14,15,11,12,17,16;BucketSortbucketSort=newBucketSort();bucketSort.sort(a,0,a.length,20);actuallyis18,but20willalsoworkfor(inti=0;iSystem.out.print(ai+,);52.九、基數(shù)排序java代碼實現(xiàn)：01./*02.*基數(shù)排序:03.*/04.importjava.util.Arrays;05.publicclassRadixSo

43、rt06.07./*08.*取數(shù)x上的第d位數(shù)字09.*paramx數(shù)*paramd第幾位，從低位到高位*return*/publicintdigit(longx,longd)longpow=1;while(d0)pow*=10;return(int)(x/pow%10);/*基數(shù)排序?qū)崿F(xiàn)，以升序排序（下面程序中的位記錄器count中，從第0個元素到第9個元素依次用來*記錄當(dāng)前比較位是0的有多少個.是9的有多少個數(shù)，而降序時則從第0個元素到第9個元素依次用來*記錄當(dāng)前比較位是9的有多少個.是0的有多少個數(shù))*paramarr待排序數(shù)組*paramdigit數(shù)組中最大數(shù)的位數(shù)*return*/p

44、ubliclongradixSortAsc(long口arr)從低位往高位循環(huán)for(intd=1;d臨時數(shù)組，用來存放排序過程中的數(shù)據(jù)longtmpArray=newlongarr.length;/位記數(shù)器，從第0個元素到第9個元素依次用來記錄當(dāng)前比較位是0的有多少個.是9的有多少個數(shù)int口count=newint10;/開始統(tǒng)計0有多少個，并存儲在第0位，再統(tǒng)計1有多少個，并存儲在第1位.依次統(tǒng)計到9有多少個for(inti=0;icountdigit(arri,d)+=1;/*42. *比如某次經(jīng)過上面統(tǒng)計后結(jié)果為：0,2,3,3,0,0,0,0,0,0則經(jīng)過下面計算后結(jié)果為：*0,2,5,8,8,8,8,8,8,8但實質(zhì)上只有如下0,2,5,8,0,0,0,0,0,0中*非零數(shù)才用到，因為其他位不存在，它們分別表示如下：2表示比較位為1的元素可以存放在索引為1、0的*位置，5表示比較位為2的元素可以存放在4、3、2三個(5-2=3)位置，8表示比較位為3的元素可以存放在*7、6、5三個(8-5=3)位置*/for(inti=1;icounti+=counti-1;/*注，這里只能從數(shù)組后往前循環(huán)，因為排序時還需保持以前的已排序好的順序，不應(yīng)該打*亂原