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

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

3、om從哪里開始排序*paramend排到哪里*paramc比較器*/publicvoidbubble(Integer口array,intfrom,intend)/需array.length1輪比較for(intk=1;k/每輪循環中從最后一個元素開始向前起泡，直到i=k止,即i等于輪次止for(inti=endfrom;i=k;i)/按照一種規則(后面元素不能小于前面元素)排序if(pareTo(arrayi-1)/如果后面元素小于了(當然是大于還是小于要看比較器實現了)前面的元素，則前后交換swap(array,i,i1);/*交換數組中的兩個元素的位置*paramarray待交換的數組*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+);另外一種實現方式：/*冒泡排序：執行完一次內for循環后，最大的一個數放到了數組的最后面。相鄰位置之間交換*/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;二、選擇排序.基本思想：每一趟從待排序的數據元素中選出最?。ɑ蜃畲螅┑囊粋€元素,順序放在已排好序的數列的最后，直到全部待排序的數據元素排完。2.排序過程：【示例】：初始關鍵字4938659776132749第一趟排序后1338659776492749第二趟排序/p>

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

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

9、smallIndex更小元素，則記下該元素的索引于smallIndex中if(pareTo(arrayminIndex)minIndex=j;先前只是記錄最小元素索引，當最小元素索引確定后，再與每輪的第一個元素交換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).基本思想：每次將一個待排序的數據元素，插入到前面已經排好序的數列中的適當位置，使數列依然有序；直到待排序數據元素全部插入完為止。.排序過程:初始關鍵字4938659776132749J=2(38)3849659776132749J=3(65)38496597

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

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

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

14、現比，其實是一樣的，只是上面先找插入點，待找到后一次性將大的元素向后移，而該算法卻*是走rH少，步一步將待排序元素往前移*/*for(inti=from;ifor(intj=i;jpare(arrayj-1,arrayj)0;j)swap(array,j,j1);*/*數組元素后移*paramarray待移動的數組*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.*排序算法的實現，對數組中指定的元素進行排序*paramarray待排序的數組*paramfrom從哪里開始排序*paramend排到哪里*paramc比較器*/publicvoidsort(Integerarray,intfrom,

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

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

18、ndex;jintegerinsertedElem=arrayi;/從有序數組中最一個元素開始查找第一個大于待插入的元素if(pareTo(insertedElem)=0)/找到插入點后，從插入點開始向后所有元素后移一位move(array,j,istep,step);arrayj=insertedElem;break;p+1)*21step=(step+1)*21;System.out.println(初始步長：+step);returnstep;/*以指定的步長將數組元素后移，步長指定每個元素間的間隔*paramarray待排序數組*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).基本思想：在當前無序區R1.H中任取一個數據元素作為比較的基準(不妨記為X),用此基準將當前無序區劃分為左右兩個較小的無序區：R1.I-1和RI+1.H，且左邊的無序子區中數據元素均小于等于基準元素，右邊的無序子區中數據元素均大于等于基準元素，而基準X則位于最終排序的位置上，即R1.I-1X.Keyhigth,則說明上次樞紐元素的位置pivot就是low或者是higth,此種情況*下分區不存，也不需處理*/if(low對

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

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

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

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

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

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

27、ivot)=0)break;else/如果低指針指向的元素小于中樞元素時繼續找low+;while(highlow)/如果高指針指向的元素小于中樞元素時表示找到，退出if(pareTo(arraypivot)break;else/如果高指針指向的元素大于中樞元素時繼續找high/退出上面循環時low=highif(low=high)break;164.swap(array,low,high);-高低指針所指向的元素排序完成后，還得要把中樞元素放到適當的位置if(pareTo(arraylow)0)如果退出循環時中樞元素大于了低指針或高指針元素時,中樞元素需與low元素交換swap(array,

28、low,pivot);pivot=low;elseif(pareTo(arraylow)swap(array,low1,pivot);pivot=low1;/返回中樞元素所在位置，以便下次分區returnpivot;184. *交換數組中的兩個元素的位置*paramarray待交換的數組*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代碼實現：*02.歸并排序：里面是一個遞歸程序，深刻理解之。03.*/04.publicclassMergeSort05.06./*07.*遞歸劃分數組08.*paramarr09.

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

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

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

33、都有未處理完的元素，所以下面兩個循環最多只有一個會執行，并且都是大于已放入臨時數組中的元素while(partlArrlndextmpArrtmpArrIndex+=arrpart1ArrIndex+;while(part2ArrIndextmpArrtmpArrIndex+=arrpart2ArrIndex+;/最后把臨時數組拷貝到源數組相同的位置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看成是一顆完全二叉樹的順序存儲結構，利用完全二叉樹中雙親結點和孩子結點之間的內在關系來選擇最小的元素。.堆的定義：N個元素的序列K1,K2K3,Kn.稱為堆，當且僅當該序列滿足特性：KiK2iKi=2;i)/根節點與最后一個葉子節點交換位置，即

35、數組中的第一個元素與最后一個元素互換swap(array,from,i1);/交換后需要重新調整堆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排序數組*paramfrom從哪*paramend到哪*paramc比較器*/privatevoidinitialHeap(Integer口arr,intfrom,intend)intlastBranchIndex=(endfrom+1)/2;/最后一個非葉子節點/對所有的非葉子節點進行循環，

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

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

38、節點三都中，最大節點不是父節點時需交換，把最大的與父節點交換，創建大頂堆if(minNodeIndex!=parentNodeIndex)swap(arr,parentNodeIndex1,minNodeIndex1);交換后可能需要重建堆，原父節點可能需要繼續下沉if(minNodeIndex*2adjustNote(arr,minNodeIndex,len);/*交換數組中的兩個元素的位置*paramarray待交換的數組*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代碼實現：01./*02.*桶式排序：03.*桶式排序不再是基于

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

41、om,intlen,intmax)inttemp=newintlen;int口count=newintmax;for(inti=0;icountkeysfrom+i+;/calculatepositioninfofor(inti=1;icounti=counti+counti-1;這意味著有多少數目小于或等于i,因此它也是position+1System.arraycopy(keys,from,temp,0,len);for(intk=len-1;k=0;k)/從最末到開頭保持穩定性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.九、基數排序java代碼實現：01./*02.*基數排序:03.*/04.importjava.util.Arrays;05.publicclassRadixSo

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

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