Java編程中完成合並排序算法的實例教程

Java編程中完成合並排序算法的實例教程。本站提示廣大學習愛好者：（Java編程中完成合並排序算法的實例教程）文章只能為提供參考，不一定能成為您想要的結果。以下是Java編程中完成合並排序算法的實例教程正文

算法概述/思緒
合並排序是基於一種被稱為“分治”（divide and conquer）的戰略。其根本思緒是如許的：
1.關於兩個有序的數組，要將其歸並為一個有序數組，我們可以很輕易地寫出以下代碼：

//both a and b is ascend.
public void merge(int[] a, int[] b, int[] c){
  int i=0,j=0,k=0;
  while (i<=a.length && j<=b.length){
    if (a[i]<=b[i]){
      c[k++]=a[i++];
    }
    else{
      c[k++]=b[j++];
    }
  }
  while (i<=a.length){
    c[k++]=a[i++];
  }
  while (j<=b.length){
    c[k++]=b[j++];
  }
}

輕易看出，如許的歸並算法是高效的，當時間龐雜度可到達O(n)。
2.假設有一個無序數組須要排序，但它的兩個完整劃分的子數組A和B分離有序，借助上述代碼，我們也能夠很輕易完成；
3.那末，假如A,B無序，怎樣辦呢？可以把它們再分紅更小的數組。
4.如斯一向劃分到最小，每一個子數組都只要一個元素，則可以視為有序數組。
5.從這些最小的數組開端，逆著下面的步調歸並歸去，全部數組就排好了。
總而言之，合並排序就是應用遞歸，先分化數組為子數組，再歸並數組。

例子
上面舉例解釋，假設要對數組a={2,1,3,5,2,3}停止排序，那末把數組劃分為{2,1,3}和{5,2,3}兩個子數組，這兩個子數組排序後變成{1,2,3}和{2,3,5}，然後對這兩個數組停止合並操作便獲得終究的有序數組。代碼完成以下：

void sort(int[] a) {
  int[] aux = new int[a.length];  //幫助數組
  mergeSort(a, 0, a.length - 1, aux);
}

void mergeSort(int[] a, int lo, int hi, int[] aux) {
  if (hi <= lo)
    return;
  int mid = lo + (hi - lo) / 2;
  mergeSort(a, lo, mid, aux);
  mergeSort(a, mid + 1, hi, aux);
  merge(a, lo, mid, hi, aux);

}

void merge(int[] a, int lo, int mid, int hi, int[] aux) {
  int i = lo, j = mid + 1;
  for (int k = lo; k <= hi; k++) {
    aux[k] = a[k];
  }
  for (int k = lo; k <= hi; k++) {
    if (i > mid)
      a[k] = aux[j++];
    else if (j > hi)
      a[k] = aux[i++];
    else if (aux[i] <= aux[j])
      a[k] = aux[i++];
    else
      a[k] = aux[j++];

  }
}

另外一種完成：自底向上的合並排序
在下面的完成中，相當於將一個年夜成績朋分成小成績分離處理，然後用一切小成績的謎底來處理全部年夜成績。將一個年夜的數組的排序劃分為小數組的排序是自頂向下的排序。還有一種完成是自底向上的排序，即先兩兩合並，然後四四合並......代碼完成以下：

void sort(int[] a) {
  int N = a.length;
  int[] aux = new int[N];
  for (int sz = 1; sz < N; sz += sz) {
    for (int lo = 0; lo < N - sz; lo += sz + sz) {
      //在每輪合並中，最初一次合並的第二個子數組能夠比第一個子數組要小
      merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1), aux);
    }
  }
}