快捷導(dǎo)航

Java編程中實現(xiàn)歸并排序算法的實例教程

更新時間：2016年05月04日 11:37:16 作者：然則

這篇文章主要介紹了Java編程中實現(xiàn)歸并排序算法的實例教程,包括自底向上的歸并排序的實現(xiàn)方法介紹,需要的朋友可以參考下

算法概述/思路
歸并排序是基于一種被稱為“分治”（divide and conquer）的策略。其基本思路是這樣的：
1.對于兩個有序的數(shù)組，要將其合并為一個有序數(shù)組，我們可以很容易地寫出如下代碼：

//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++];
  }
}

容易看出，這樣的合并算法是高效的，其時間復(fù)雜度可達到O(n)。
2.假如有一個無序數(shù)組需要排序，但它的兩個完全劃分的子數(shù)組A和B分別有序，借助上述代碼，我們也可以很容易實現(xiàn)；
3.那么，如果A,B無序，怎么辦呢？可以把它們再分成更小的數(shù)組。
4.如此一直劃分到最小，每個子數(shù)組都只有一個元素，則可以視為有序數(shù)組。
5.從這些最小的數(shù)組開始，逆著上面的步驟合并回去，整個數(shù)組就排好了。
總而言之，歸并排序就是使用遞歸，先分解數(shù)組為子數(shù)組，再合并數(shù)組。

例子
下面舉例說明，假如要對數(shù)組a={2,1,3,5,2,3}進行排序，那么把數(shù)組劃分為{2,1,3}和{5,2,3}兩個子數(shù)組，這兩個子數(shù)組排序后變?yōu)閧1,2,3}和{2,3,5}，然后對這兩個數(shù)組進行歸并操作便得到最終的有序數(shù)組。代碼實現(xiàn)如下：

void sort(int[] a) {
  int[] aux = new int[a.length];  //輔助數(shù)組
  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++];

  }
}

另一種實現(xiàn)：自底向上的歸并排序
在上面的實現(xiàn)中，相當(dāng)于將一個大問題分割成小問題分別解決，然后用所有小問題的答案來解決整個大問題。將一個大的數(shù)組的排序劃分為小數(shù)組的排序是自頂向下的排序。還有一種實現(xiàn)是自底向上的排序，即先兩兩歸并，然后四四歸并......代碼實現(xiàn)如下：

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) {
      //在每輪歸并中，最后一次歸并的第二個子數(shù)組可能比第一個子數(shù)組要小
      merge(a, lo, lo + sz - 1, Math.min(lo + sz + sz - 1, N - 1), aux);
    }
  }
}

您可能感興趣的文章: