Java實(shí)現(xiàn)基本排序算法的示例代碼

第Java實(shí)現(xiàn)基本排序算法的示例代碼目錄1.概述2.插入排序2.1直接插入排序2.2希爾排序（縮小增量排序）3.選擇排序3.1直接選擇排序3.2堆排序4.交換排序4.1冒泡排序4.2快速排序5.歸并排序6.計數(shù)排序（非比較類型的排序）7.排序算法總結(jié)

1.概述

排序概念：就是將一串記錄按照其中某個或某些關(guān)鍵字的大小，遞增或遞減的排列起來的操作。

穩(wěn)定性：通俗的將就是數(shù)據(jù)元素不發(fā)生有間隔的交換，例如：

內(nèi)部排序：數(shù)據(jù)元素全部放在內(nèi)存中的排序

外部排序：數(shù)據(jù)元素太多不能一次加載到內(nèi)存中，根據(jù)排序過程的要求不能在內(nèi)外存之間移動數(shù)據(jù)的排序。

注意：以下的排序默認(rèn)排升序。默認(rèn)待排序列為：2，5，1，3，8，6，9，4，7，0，6

2.插入排序

把待排序的記錄按其關(guān)鍵碼值的大小逐個插入到一個已經(jīng)排好序的有序序列中，直到所有的記錄插入完為止，得到一個新的有序序列

2.1直接插入排序

1.思想：

對于一個元素，將其與前面元素進(jìn)行比較，將其插入到合適的位置。

排升序：將待排元素依次與序列中元素從右往左比，若待排元素小，則繼續(xù)往前比，找到合適位置插入，原來元素的位置按順序往后搬移。

2.畫圖說明：

說明：第一個元素默認(rèn)它有序，所以從第二個元素開始進(jìn)行比較然后插入，5比2大，繼續(xù)下一個，將1依次比較插入2前面，將3依次比較插入5前面，8比5大，不用管，繼續(xù)下一個，將6依次比較插在8面，9比8大，不用管，將7依次比較，插在8前面，將0依次比較插在1前面，將6依次比較插在7前面，插入完成。

3.代碼展示：

publicclassInsertSort{

publicstaticvoidinsertSort(int[]array){

for(inti=1;iarray.length;i++){//讓從1下標(biāo)開始，因?yàn)槿绻挥幸粋€元素，它自己默認(rèn)有序

intkey=array[i];//從數(shù)組中的第二個元素開始比較，進(jìn)行插入

intend=i-1;//end的位置是要插入元素的前一個位置

while(end=0keyarray[end]){//end不能越界，找待插入的位置，此處注意：key不能小于等于array[end]，否則為不穩(wěn)定

array[end+1]=array[end];

end--;

array[end+1]=key;//找到位置進(jìn)行插入，因?yàn)樯厦鎒nd--了，所以這里要插入的位置為end+1

publicstaticvoidmain(String[]args){

int[]array={2,5,1,3,8,6,9,4,7,0,6};

insertSort(array);

for(inti:array){

System.out.print(i+"");

結(jié)果：

4.特性總結(jié)：

時間復(fù)雜度：循環(huán)嵌套，O(N^2)，最優(yōu)情況：當(dāng)序列接近有序，插入的元素比較少，為O(N)

空間復(fù)雜度：不借助輔助空間，O(1)

穩(wěn)定性：數(shù)據(jù)元素不發(fā)生有間隔的交換，穩(wěn)定

應(yīng)用場景：數(shù)據(jù)量小，接近有序

2.2希爾排序（縮小增量排序）

1.思想：

選一個整數(shù)為數(shù)據(jù)元素的間隔，將間隔相同的數(shù)據(jù)元素分為一組，分別對這些組進(jìn)行插入排序，間隔減小，重復(fù)上述操作，當(dāng)間隔減少到1的時候，數(shù)據(jù)元素即排好序了。

2.畫圖說明：

說明：gap為間隔，這里依次將gap=4，2，1，先把間隔為4的數(shù)據(jù)元素用插入排序排好序，再利用插入排序排gap=2的數(shù)據(jù)元素，依次重復(fù)上述操作，即可。

3.代碼展示：

publicclassShellSort{

publicstaticvoidshellSort(int[]array){

intgap=array.length;

while(gap1){

gap=gap/3+1;

for(inti=gap;iarray.length;i++){//跟插入排序一樣，都從一組數(shù)的第二個元素開始，因?yàn)榈谝粋€數(shù)默認(rèn)有序

intkey=array[i];

intend=i-gap;//end的位置也是代排數(shù)的前一個，但這里間隔為gap，所以前一個位置為i-gap

while(end=0keyarray[end]){//與插入排序保持不變,找待插入的位置

array[end+gap]=array[end];//key小于前一個數(shù)，讓end位置的元素往后移一位，

end-=gap;//end每次向左走的時候一次走gap的間隔

array[end+gap]=key;//找到待排位置將key插入相應(yīng)位置

publicstaticvoidmain(String[]args){

int[]array={2,5,1,3,8,6,9,4,7,0,6};

shellSort(array);

for(inti:array){

System.out.print(i+"");

結(jié)果：

4.特性總結(jié)：

希爾排序是對直接插入排序的優(yōu)化。

當(dāng)gap1時都是預(yù)排序，目的是讓數(shù)組元素接近有序，當(dāng)gap==1時，數(shù)組已經(jīng)接近有序了，這樣插入排序?qū)芸欤w而言，達(dá)到了優(yōu)化的效果。

希爾排序的時間復(fù)雜度不好計算，因?yàn)間ap的取值方法很多，導(dǎo)致很難去計算。

gap的取法有多種，最初shell提出取gap=n/2，gap=gap/2，直到gap=1，后來，Kunth提出取gap=[gap/3]+1。在Kunth所著的《計算機(jī)程序設(shè)計技巧》第3卷中，利用大量的實(shí)驗(yàn)統(tǒng)計資料得出，當(dāng)n很大時，關(guān)鍵碼的平均比較次數(shù)和對象平均移動次數(shù)大約在n^1.25到1.6n^1.25范圍內(nèi)，這是利用直接插入排序作為子序列排序方法的情況下得到的。

故時間復(fù)雜度暫記為：O(N^1.25)~O(1.6N^1.25)

空間復(fù)雜度：沒有借助輔助空間，O(1)

穩(wěn)定性：數(shù)據(jù)元素發(fā)生了有間隔的交換，不穩(wěn)定

應(yīng)用場景：數(shù)據(jù)比較隨機(jī)

3.選擇排序

每一次從待排數(shù)據(jù)元素中選出最?。ㄗ畲螅┑脑?，存放在序列的起始（末尾）位置，直到全部待排序的數(shù)據(jù)元素全部排完。

3.1直接選擇排序

1.思想：

思路1：

找出序列中的最大的元素，若它不在序列的末尾，將它與末尾元素交換位置，依次循環(huán)。

思路2：

每次找元素的時候，找一個最大的和一個最小的，最大的和最后一個交換位置，最小的和第一個交換位置，依次循環(huán)

2.畫圖說明：

思路1：

說明：先找到序列的最大元素與序列最后一個元素交換，序列的最后的位置朝前移一個，再找新序列的最大元素再與最后一個交換位置，依次循環(huán)。

思路2：

說明：這種方法是一次找兩個元素，跟上面那種本質(zhì)上一樣，只是一次交換了兩個元素，將最大的與最后一個交換，將最小的與第一個交換

3.代碼展示：

publicclassSelectSort{

publicstaticvoidselectSort1(int[]array){

intsize=array.length;

for(inti=0;isize-1;i++){//選擇的趟數(shù)，size-1是因?yàn)楫?dāng)選擇到序列剩一個元素時就不用選了

intpos=0;//pos標(biāo)記最大元素的位置，剛開始是默認(rèn)為第一個位置

for(intj=1;jsize-i;j++){//j=1是因?yàn)槟J(rèn)第一個元素的位置為最大元素的位置，所以從第二個元素的位置開始比較

//size-i是因?yàn)槊刻诉x擇完后，序列都要減少一個

if(array[j]array[pos]){

pos=j;//找到最大元素位置，更新pos

if(pos!=size-i-1){//如果最大元素的位置剛好是最后一個位置，則不需要交換，反之進(jìn)行交換

swap(array,pos,size-i-1);

publicstaticvoidselectSort2(int[]array){

intleft=0;//序列的左邊界

intright=array.length-1;//序列的右邊界

while(leftright){//當(dāng)序列中至少存在倆元素時

intminPos=left;//剛開始將最小元素的位置設(shè)定為序列的第一個位置

intmaxPos=left;//剛開始將最大元素的位置也設(shè)定為序列的第一個位置

intindex=left+1;//從序列的第二個元素開始找最大元素和最小元素的位置

//找最大元素和最小元素的位置

while(index=right){

if(array[index]array[minPos]){

minPos=index;

if(array[index]array[maxPos]){

maxPos=index;

index++;

if(minPos!=left){//當(dāng)最小的元素不在序列的最左端時交換位置

swap(array,minPos,left);

//這里我是先交換最小的元素，但是如果最大的元素在最左側(cè)，那么會將maxPos位置的元素更新為最小的元素，導(dǎo)致后面

//交換最大元素的時候maxPos標(biāo)記的元素不準(zhǔn)確，所以下面將maxPos的位置更新了一下

//注意：如果是先交換最大的元素，則更新minPos的位置

if(maxPos==left){

maxPos=minPos;

//if(minPos==right){

//minPos=maxPos;

//}

if(maxPos!=right){//當(dāng)最大元素不在序列的最右端時交換位置

swap(array,maxPos,right);

left++;//左邊界+1

right--;//右邊界-1

publicstaticvoidswap(int[]array,inta,intb){

intt=array[a];

array[a]=array[b];

array[b]=t;

publicstaticvoidmain(String[]args){

int[]array={9,5,1,3,8,6,2,4,7,6,0};

selectSort1(array);

for(inti:array){

System.out.print(i+"");

System.out.println();

selectSort2(array);

for(inti:array){

System.out.print(i+"");

4：特性總結(jié)：

時間復(fù)雜度：找元素，交換元素是循環(huán)嵌套，O(N^2)

空間復(fù)雜度：沒有借助輔助空間，O(1)

穩(wěn)定性：數(shù)據(jù)元素存在有間隔的交換，不穩(wěn)定

缺陷：找最大元素或者最小元素的時候重復(fù)比較

3.2堆排序

1.思想：

堆排序是利用堆積樹（堆）這種數(shù)據(jù)結(jié)構(gòu)設(shè)計的一種算法，它是選擇排序的一種，它是通過堆來進(jìn)行選擇數(shù)據(jù)。

注意：排升序，建大根堆，排降序，建小根堆。

堆排序分為兩部分：建堆，利用向下調(diào)整建堆，再利用堆刪除的思想排序。

向下調(diào)整：

前提：要調(diào)整的節(jié)點(diǎn)的兩個左右子樹都已滿足堆的特性

方法：建大堆，將根的元素與左右孩子較大的元素交換，建小堆，將根的元素與左右孩子較小的元素交換

堆刪除思想：

將堆頂元素與最后一個元素交換位置

堆中有效元素減少一個

再對堆頂元素向下調(diào)整

2.畫圖說明：

因?yàn)閿?shù)據(jù)元素多，二叉樹的圖看著不太清晰，所以我用以下序列：0，5，3，4，1，2

建堆：

利用堆刪除思想排序：

3.代碼展示：

publicclassHeapSort{

//向下調(diào)整

publicstaticvoidshiftDown(int[]array,intparent,intsize){

intchild=parent*2+1;//默認(rèn)將左孩子設(shè)為parent的孩子，因?yàn)椴恢烙疫吅⒆邮欠翊嬖?/p>

while(childsize){

if(child+1sizearray[child+1]array[child]){//如果右孩子存在，比較哪個孩子值大

child+=1;//將child設(shè)為較大的孩子

if(array[parent]array[child]){//如果parent小，將parent與child交換

swap(array,parent,child);

parent=child;//更新parent

child=parent*2+1;//更新child

}else{//如果已經(jīng)滿足堆特性則直接返回

return;

//堆排序

publicstaticvoidheapSort(int[]array){

//建堆

intsize=array.length;

intlastLeaf=((size-1)-1)/2;//找到倒數(shù)第一個非葉子節(jié)點(diǎn)

for(introot=lastLeaf;rootroot--){//從該結(jié)點(diǎn)開始，依次向下調(diào)整直到根節(jié)點(diǎn)

shiftDown(array,root,size);

//利用堆刪除思想排序,從最后一個元素開始與堆頂元素交換，然后對堆頂元素進(jìn)行向下調(diào)整

intend=size-1;

while(end0){

swap(array,0,end);

shiftDown(array,0,end);

end--;

publicstaticvoidswap(int[]array,inta,intb){

intt=array[a];

array[a]=array[b];

array[b]=t;

publicstaticvoidmain(String[]args){

int[]array={2,5,1,3,8,6,9,4,7,0,6};

heapSort(array);

for(inti:array){

System.out.print(i+"");

結(jié)果：

4.特性總結(jié)：

時間復(fù)雜度：n個元素進(jìn)行比較，而且太向下調(diào)整，調(diào)整的深度為完全二叉樹的深度，故時間復(fù)雜度為：O(NlogN),logN是log以2為底的N

空間復(fù)雜度：沒有借助輔助空間，O(1)

穩(wěn)定性：元素發(fā)生了有間隔的交換，不穩(wěn)定

應(yīng)用場景：求前k個最小或者最大，可以和其他排序結(jié)合起來增加效率

4.交換排序

基本思想就是根據(jù)序列中兩個記錄鍵值的比較結(jié)果來交換這兩個記錄在序列中的位置，交換排序的特點(diǎn)是：將鍵值較大的記錄向序列的尾部移動，鍵值較小的記錄向序列的前部移動

4.1冒泡排序

1.思想：

依次將序列元素進(jìn)行比較，若array[i]array[i+1],交換兩個元素的位置，直到最后一個元素，從中可以得出，每躺冒泡只能確定一個元素的位置，若序列有n個元素，則需要進(jìn)行n-1躺冒泡，因?yàn)樾蛄凶詈笠粋€元素的位置不用確定。

從比較的次數(shù)可以看出：第一躺比較的次數(shù)為n-1，第二躺的比較次數(shù)為n-2.....即每趟冒泡比較的次數(shù)在遞減，即比較次數(shù)是為n-1-i，i為冒泡的趟數(shù)。

2.畫圖說明：

3.冒泡排序的優(yōu)化：

從上圖可以看出第10躺冒泡沒有進(jìn)行，因?yàn)樾蛄幸呀?jīng)有序，即數(shù)據(jù)元素不在發(fā)生交換。

優(yōu)化：在每趟進(jìn)行的開始給一個標(biāo)記isChage=false，如果該躺冒泡發(fā)生了元素交換，將isChange=true，在每趟冒泡完進(jìn)行判斷，如果是Change==false，即沒有發(fā)生交換，說明序列已經(jīng)有序，即不用在繼續(xù)冒泡，直接返回即可。

4.代碼展示：

publicclassBubbleSort{

publicstaticvoidbubbleSort(int[]array){

intsize=array.length;

for(inti=0;isize-1;i++){

booleanisChange=false;//為了優(yōu)化冒泡排序給的標(biāo)記，當(dāng)元素不發(fā)生交換的時候說明已經(jīng)有序

for(intj=0;jsize-1-i;j++){

if(array[j+1]array[j]){

swap(array,j,j+1);

isChange=true;

if(isChange==false){//如果元素不發(fā)生交換，直接返回

return;

publicstaticvoidswap(int[]array,inta,intb){

intt=array[a];

array[a]=array[b];

array[b]=t;

publicstaticvoidmain(String[]args){

int[]array={2,5,1,3,8,6,9,4,7,0,6};

bubbleSort(array);

for(inti:array){

System.out.print(i+"");

結(jié)果：

5.特性總結(jié)：

時間復(fù)雜度：冒泡的趟數(shù)，每趟的比較次數(shù)，O(N^2)

空間復(fù)雜度：不借助輔助空間，O(1)

穩(wěn)定性：數(shù)據(jù)元素雖然發(fā)生了交換，但是沒有間隔交換，穩(wěn)定

4.2快速排序

4.2.1.思想

快速排序是Hoare提出的一種二叉樹結(jié)構(gòu)的交換排序方法。

基本思想為：任取待排元素序列中的某個元素作為基準(zhǔn)值（這里我們?nèi)∽钣覀?cè)元素為基準(zhǔn)值），按照該基準(zhǔn)值將序列劃分為兩個區(qū)間，左側(cè)比基準(zhǔn)值小，右側(cè)比基準(zhǔn)值大，再分別用快速排序遞歸排左區(qū)間和右區(qū)間。

參考代碼：

publicstaticvoidquickSort(int[]array,intleft,intright){//左閉右開

if(right-left1){//遞歸的返回條件，區(qū)間最少得有兩個元素

intdiv=partition(array,left,right);

quickSort(array,left,div);//遞歸排左側(cè)

quickSort(array,div+1,right);//遞歸排右側(cè)

故只要實(shí)現(xiàn)分割方法即可。

4.2.2三種分割方式

1.Hoare法

思想：在左邊找比基準(zhǔn)值大的，右邊找比基準(zhǔn)值小的，兩個交換位置，最后將較大一側(cè)的第一個元素與基準(zhǔn)值交換位置。

畫圖說明：

參考代碼：

//分割區(qū)間方法1：hoare：左邊找比基準(zhǔn)值大的，右邊找比基準(zhǔn)值小的，兩個交換位置,最后再將基準(zhǔn)值放到中間的位置

publicstaticintpartition1(int[]array,intleft,intright){

intkey=array[right-1];//找基準(zhǔn)值，以最右側(cè)元素為基準(zhǔn)值

intbegin=left;//在左側(cè)找的下標(biāo)

intend=right-1;//在右側(cè)找的下標(biāo)

while(beginend){

while(array[begin]=keybeginend){//左側(cè)找大的，不能越界

begin++;

while(array[end]=keyendbegin){//右側(cè)找小的，不能越界

end--;

if(begin!=end){

swap(array,begin,end);//begin與end不在同一位置的時候交換，否則沒有交換的必要

if(begin!=right-1){

swap(array,begin,right-1);//將基準(zhǔn)值與begin位置的元素交換，begin或者end都行

returnend;//將分割的位置返回，begin與end都可以

2.挖坑法

思想：將基準(zhǔn)值存入key中，基準(zhǔn)值的位置為第一個坑位，在左側(cè)找比基準(zhǔn)值大的，放到第一個坑位上，此時這個元素的原始位置又形成了一個新的坑位，再從右側(cè)找比基準(zhǔn)值小的，放到前面的坑位上，依次循環(huán)，即將序列分割為兩部分。

畫圖說明：

參考代碼：

//分割區(qū)間方法二：挖坑法：基準(zhǔn)值是一個坑位，左側(cè)找大的放到基準(zhǔn)值的坑位上，此時形成了新的坑位，再在右側(cè)找小的放到上一個坑位，依次循環(huán)

publicstaticintpartition2(int[]array,intleft,intright){

intkey=array[right-1];//取最右側(cè)元素為基準(zhǔn)值，end的位置形成了第一個坑位

intbegin=left;

intend=right-1;

while(beginend){

while(beginendkey=array[begin]){//在左側(cè)找比基準(zhǔn)值大的

begin++;

if(beginend){

array[end]=array[begin];//填end坑位，重新生成begin坑位

while(beginendkey=array[end]){//在右側(cè)找比基準(zhǔn)值小的

end--;

if(beginend){

array[begin]=array[end];//填begin坑位，重新生成end坑位

array[begin]=key;//將基準(zhǔn)值填充在最后一個坑位

returnend;

3.前后標(biāo)記法

思想：給兩個標(biāo)記cur，pre，pre標(biāo)記cur的前一個，cur開始標(biāo)記第一個元素，依次往后走，cur小于區(qū)間的右邊界，如果cur小于基準(zhǔn)值并且++pre不等于cur交換cur與pre位置的元素，最后交換++pre與基準(zhǔn)值位置的元素。

畫圖說明：

參考代碼：

//分割區(qū)間方法三：前后標(biāo)記法

publicstaticintpartition3(int[]array,intleft,intright){

intkey=array[right-1];

intcur=left;

intpre=cur-1;

while(curright){

if(array[cur]key++pre!=cur){//當(dāng)cur位置的元素小于基準(zhǔn)值并且++pre！=cur的時候，交換

swap(array,cur,pre);

cur++;

if(++pre!=right-1){//++pre為與基準(zhǔn)值交換的位置，所以當(dāng)++pre！=right-1的時候，交換基準(zhǔn)值的位置

swap(array,pre,right-1);

returnpre;

4.2.3快速排序的優(yōu)化

快速排序的優(yōu)化：對基準(zhǔn)值的選取進(jìn)行優(yōu)化，這樣做是為了選取的基準(zhǔn)值盡可能的將區(qū)間的左右側(cè)分的均勻一點(diǎn)兒。

優(yōu)化方法：三數(shù)取中法取基準(zhǔn)值，三數(shù)：區(qū)間的中間元素，最左側(cè)元素，最右側(cè)元素，取它們?nèi)齻€的中間值。

參考代碼：

//快排優(yōu)化：三數(shù)取中法來取基準(zhǔn)值，左側(cè)，右側(cè)，中間這三個數(shù)的中間值來作為基準(zhǔn)值,這里返回的是基準(zhǔn)值下標(biāo)

publicstaticintgetIndexOfMid(int[]array,intleft,intright){

intmid=left+((right-left)1);

if(array[left]array[right-1]){//最右側(cè)的下標(biāo)為right-1

if(array[mid]array[left]){

returnleft;

}elseif(array[mid]array[right-1]){

returnright-1;

}else{

returnmid;

}else{

if(array[mid]array[right-1]){

returnright-1;

}elseif(array[mid]array[left]){

returnleft;

}else{

returnmid;

具體與之前代碼結(jié)合方式，我這里選取一種分割方法來進(jìn)行優(yōu)化：

參考代碼：

//分割區(qū)間方法三：前后標(biāo)記法

publicstaticintpartition3(int[]array,intleft,intright){

intindex=getIndexOfMid(array,left,right);//用三數(shù)取中法獲得基準(zhǔn)值的下標(biāo)

if(index!=right-1){

swap(array,index,right-1);//如果下表不在最右側(cè)就交換

intkey=array[right-1];

intcur=left;

intpre=cur-1;

while(curright){

if(array[cur]key++pre!=cur){//當(dāng)cur位置的元素小于基準(zhǔn)值并且++pre！=cur的時候，交換

swap(array,cur,pre);

cur++;

if(++pre!=right-1){//++pre為與基準(zhǔn)值交換的位置，所以當(dāng)++pre！=right-1的時候，交換基準(zhǔn)值的位置

swap(array,pre,right-1);

returnpre;

4.2.4快速排序的非遞歸方式

非遞歸的快速排序借助棧這一數(shù)據(jù)結(jié)構(gòu)

參考代碼：

//非遞歸的快速排序，利用棧來保存分割的區(qū)間，傳參只需要傳數(shù)組即可

publicstaticvoidquickSort(int[]array){

StackIntegers=newStack();

s.push(array.length);

s.push(0);

while(!s.empty()){

intleft=s.pop();

intright=s.pop();

if(right-left==0){

continue;

intdiv=partition(array,left,right);

s.push(right);

s.push(div+1);

s.push(div);

s.push(left);

4.2.5快速排序的特性總結(jié)

時間復(fù)雜度：有比較，遞歸，O(NlogN)

空間復(fù)雜度：存在遞歸，遞歸的深度為完全二叉樹的深度，O(logN)

穩(wěn)定性：數(shù)據(jù)元素發(fā)生有間隔的交換，不穩(wěn)定

應(yīng)用場景：數(shù)據(jù)凌亂且隨機(jī)

5.歸并排序

1.思想：

歸并排序是將兩個有序序列進(jìn)行合并，但是我們拿到是一個數(shù)組，所以得先將數(shù)組遞歸均分為兩部分，再將兩部分進(jìn)行合并。

2.畫圖說明：

遞歸均分：

從下往上合并：

3.代碼展示：

publicclassMergeSort{

publicstaticvoidmergeSort(int[]array,intleft,intright,int[]temp){

if(right-left1){

intmid=left+((right-left)1);

mergeSort(array,left,mid,temp);//遞歸均分左側(cè)

mergeSort(array,mid,right,temp);//遞歸均分右側(cè)

mergeData(array,left,mid,right,temp);//合并兩個序列，[left,mid),[mid,right)

System.arraycopy(temp,left,array,left,right-left);//拷貝到原數(shù)組，源，起始位置，新，起始位置，長度

publicstaticvoidmergeData(int[]array,intleft,intmid,intright,int[]temp){

//[begin1,end1),[begin2,end2),為兩個合并的區(qū)間

intbegin1=left;

intend1=mid;

intbegin2=mid;

intend2=right;

intindex=left;//輔助數(shù)組的下標(biāo)

while(begin1end1begin2end2){

if(array[begin1]=array[begin2]){

temp[index++]=array[begin1++];

}else{

temp[index++]=array[begin2++];

while(begin1end1){

temp[index++]=array[begin1++];

while(begin2end2){

temp[index++]=array[begin2++];

//重新包裝一下，便于用戶傳參

publicstaticvoidmergeSort(int[]array){

int[]temp=newint[array.length];

mergeSort(array,0,array.length,temp);

4.非遞歸的歸并排序

給一個間隔，用間隔來表示區(qū)間

參考代碼：

//非遞歸的歸并排序

publicstaticvoidmergeSortNor(int[]array){

intsize=array.length;

int[]temp=newint[size];

intgap=1;//先每兩個元素歸并

while(gapsize){

for(inti=0;isize;