歸并排序（四）

import java.util.Arrays;
/**
 * 
 * @author Administrator
 *歸并排序原理：對于給定的一組記錄（假設共有n個記錄），首先将每兩個相鄰的長度為1的子序列進行歸并，得到
 *n/2（向上取整）個長度為2或者1的有序子序列，再将其兩兩歸并，反複執行此過程，直到得到一個有序序列
 *關鍵的兩步：1、劃分半子表；2、合并半子表
 */
public class MergeSort {
  /**
   * 
   * @param arry  表示原始數組
   * @param p   表示數組首元素下标
   * @param q   表示數組平分取整的中間值
   * @param r   表示數組尾元素的下标
   */
  public static void merge(int arry[],int p,int q,int r){
    int i,j,k,n1,n2;  //n1,n2用來确定兩個劃分數組的大小
    n1 = q+1-p; 
    n2 = r-q;
    int[] L = new int[n1];
    int[] R = new int[n2];
    //根據劃分規則，将原始數組平分為L，R
    for(i=0,k=p;i<n1;i++,k++){
      L[i] = arry[k];
    }
    for(i=0,k=q+1;i<n2;i++,k++){
      R[i] = arry[k];
    }
    
    //對兩個數組按照一定的順序進行合并。并将合并後的資料存入到原始的數組中，此處按照從小到大排序
    for(i=0,j=0,k=p;i<n1&&j<n2;k++){  //注意這裡每次增長的隻是原始數組，L和R數組的移動是在每次比較時候
      if(L[i]>R[j]){
        arry[k] = R[j];
        j++;  //移動
      }else {
        arry[k] =L[i];
        i++;  //移動
      }
        
    }
    //如果L、R中有數組為空，直接将另一個數組中的元素取出并放入到原始數組中
    while(i<n1){
      arry[k++] = L[i++];
    }
    while(j<n2){
      arry[k++] = R[j++];
    }
  }
  
  /**
   * 
   * @param arry 原始數組
   * @param p   數組首元素下标
   * @param r   數組尾元素下标
   * 歸并排序核心：先遞歸，再合并
   */
  public static void mergeSort(int arry[],int p,int r){
    if(p<r){  //遞歸的終止條件，相當重要
    int q=(p+r)/2;
    mergeSort(arry, p, q);
    mergeSort(arry, q+1, r);
    merge(arry, p, q, r);
    }
  }

  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int a[] ={0,9,8,7,6,5,4,3,2,1};
    mergeSort(a, 0, 9);
    System.out.println(Arrays.toString(a));
  }

}
      

運作結果：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]