Java排序算法三之歸并排序的遞歸與非遞歸的案例分析？這個(gè)問題可能是我們?nèi)粘W(xué)習(xí)或工作經(jīng)常見到的。希望通過這個(gè)問題能讓你收獲頗深。下面是小編給大家?guī)淼膮⒖純?nèi)容，讓我們一起來看看吧！

從策劃到設(shè)計(jì)制作，每一步都追求做到細(xì)膩，制作可持續(xù)發(fā)展的企業(yè)網(wǎng)站。為客戶提供網(wǎng)站設(shè)計(jì)制作、成都網(wǎng)站制作、網(wǎng)站策劃、網(wǎng)頁設(shè)計(jì)、空間域名、虛擬空間、網(wǎng)絡(luò)營銷、VI設(shè)計(jì)、 網(wǎng)站改版、漏洞修補(bǔ)等服務(wù)。為客戶提供更好的一站式互聯(lián)網(wǎng)解決方案,以客戶的口碑塑造優(yōu)易品牌,攜手廣大客戶,共同發(fā)展進(jìn)步。

歸并有遞歸和非遞歸兩種。

歸并的思想是：
1.將原數(shù)組首先進(jìn)行兩個(gè)元素為一組的排序，然后合并為四個(gè)一組，八個(gè)一組，直至合并整個(gè)數(shù)組；
2.合并兩個(gè)子數(shù)組的時(shí)候，需要借助一個(gè)臨時(shí)數(shù)組，用來存放當(dāng)前的歸并后的兩個(gè)數(shù)組；
3.將臨時(shí)數(shù)組復(fù)制回原數(shù)組對(duì)應(yīng)的位置。

非遞歸的代碼如下：

package mergesort;

import java.util.Arrays;
import java.util.Random;
import java.util.Scanner;
//歸并排序的非遞歸算法
public class MergeSort{
  public static void main(String args[]){
    MergeSort mer = new MergeSort();
    int[] array = mer.getArray();
    System.out.println("OriginalArray:" + Arrays.toString(array));
    mer.mergeSort(array);
    System.out.println("SortedArray:" + Arrays.toString(array));
  }
  public int[] getArray(){
    Scanner cin = new Scanner(System.in);
    System.out.print("Input the length of Array:");
    int length = cin.nextInt();
    int[] arr = new int[length];
    Random r = new Random();
    for(int i = 0; i < length; i++){
      arr[i] = r.nextInt(100);
    }
    cin.close();
    return arr;
  }
  public void mergeSort(int[] a){
    int len = 1;
    while(len < a.length){
      for(int i = 0; i < a.length; i += 2*len){
        merge(a, i, len);
      }
      len *= 2;
    }
  }

  public void merge(int[] a, int i, int len){
    int start = i;
    int len_i = i + len;//歸并的前半部分?jǐn)?shù)組
    int j = i + len;
    int len_j = j +len;//歸并的后半部分?jǐn)?shù)組
    int[] temp = new int[2*len];
    int count = 0;
    while(i < len_i && j < len_j && j < a.length){
      if(a[i] <= a[j]){
        temp[count++] = a[i++];
      }
      else{
        temp[count++] = a[j++];
      }
    }
    while(i < len_i && i < a.length){//注意：這里i也有可能超過數(shù)組長度
      temp[count++] = a[i++];
    }
    while(j < len_j && j < a.length){
      temp[count++] = a[j++];
    }
    count = 0;
    while(start < j && start < a.length){
      a[start++] = temp[count++];
    }
  }
}

名稱欄目：Java排序算法三之歸并排序的遞歸與非遞歸的案例分析-創(chuàng)新互聯(lián)
網(wǎng)址分享：http://www.weahome.cn/article/djhpeh.html