本文實(shí)例講述了java數(shù)據(jù)結(jié)構(gòu)排序算法之歸并排序。分享給大家供大家參考，具體如下：

在前面說(shuō)的那幾種排序都是將一組記錄按關(guān)鍵字大小排成一個(gè)有序的序列，而歸并排序的思想是：基于合并，將兩個(gè)或兩個(gè)以上有序表合并成一個(gè)新的有序表

歸并排序算法：假設(shè)初始序列含有n個(gè)記錄，首先將這n個(gè)記錄看成n個(gè)有序的子序列，每個(gè)子序列長(zhǎng)度為1,然后兩兩歸并，得到n/2個(gè)長(zhǎng)度為2（n為奇數(shù)的時(shí)候，最后一個(gè)序列的長(zhǎng)度為1）的有序子序列。在此基礎(chǔ)上，再對(duì)長(zhǎng)度為2的有序子序列進(jìn)行亮亮歸并，得到若干個(gè)長(zhǎng)度為4的有序子序列。如此重復(fù)，直到得到一個(gè)長(zhǎng)度為n的有序序列為止。這種方法被稱作是：2-路歸并排序（基本操作是將待排序列中相鄰的兩個(gè)有序子序列合并成一個(gè)有序序列）。

算法實(shí)現(xiàn)代碼如下：

package exp_sort;
public class MergeSort {
  /**
   * 相鄰兩個(gè)有序子序列的合并算法
   *
   * @param src_array
   * @param low
   * @param high
   * @param des_array
   */
  public static void Merge(int src_array[], int low, int high,
      int des_array[]) {
    int mid;
    int i, j, k;
    mid = (low + high) / 2;
    i = low;
    k = 0;
    j = mid + 1;
    // compare two list
    while (i <= mid && j <= high) {
      if (src_array[i] <= src_array[j]) {
        des_array[k] = src_array[i];
        i = i + 1;
      } else {
        des_array[k] = src_array[j];
        j = j + 1;
      }
      k = k + 1;
    }
    // if 1 have,cat
    while (i <= mid) {
      des_array[k] = src_array[i];
      k = k + 1;
      i = i + 1;
    }
    while (j <= high) {
      des_array[k] = src_array[j];
      k = k + 1;
      j = j + 1;
    }
    for (i = 0; i < k; i++) {
      src_array[low + i] = des_array[i];
    }
  }
  /**
   * 2-路歸并排序算法，遞歸實(shí)現(xiàn)
   *
   * @param src_array
   * @param low
   * @param high
   * @param des_array
   */
  public static void mergeSort(int src_array[], int low, int high,
      int des_array[]) {
    int mid;
    if (low < high) {
      mid = (low + high) / 2;
      mergeSort(src_array, low, mid, des_array);
      mergeSort(src_array, mid + 1, high, des_array);
      Merge(src_array, low, high, des_array);
    }
  }
  public static void main(String[] args) {
    // TODO Auto-generated method stub
    int array1[] = { 38, 62, 35, 77, 55, 14, 35, 98 };
    int array2[] = new int[array1.length];
    mergeSort(array1, 0, array1.length - 1, array2);
    System.out.println("\n----------after sort-------------");
    for (int ii = 0; ii < array1.length; ii++) {
      System.out.print(array1[ii] + " ");
    }
    System.out.println("\n");
  }
}

代碼解釋：

歸并排序中一趟歸并要多次調(diào)用到2-路歸并算法，一趟的歸并的時(shí)間復(fù)雜度是O(n)，合并兩個(gè)已經(jīng)排好序的表的時(shí)間顯然是線性的，因?yàn)樽疃噙M(jìn)行了n-1次比較，其中n是元素的總數(shù)。如果有多個(gè)數(shù)，即n不為1時(shí)，遞歸的將前半部分?jǐn)?shù)據(jù)和后半部分?jǐn)?shù)據(jù)各自歸并排序，得到排序后的兩部分?jǐn)?shù)據(jù)，再合并到一起。

算法分析：

該算法是建立在歸并操作（也叫歸并算法，指的是將兩個(gè)已經(jīng)排序的序列合并成一個(gè)序列的操作）上的一種有效的排序算法。該算法是采用分治法（Divide and Conquer）的一個(gè)非常典型的應(yīng)用，它將問(wèn)題分成一些小的問(wèn)題然后遞歸求解，而治的階段則是將分的階段解得的各個(gè)答案修補(bǔ)到一塊；分治是遞歸非常有力的用法。注意：與快速·排序和堆排序比較，歸并排序最大的特點(diǎn)就是，它一種穩(wěn)定的排序方法。速度僅次于快速排序，一般用于對(duì)總體無(wú)序，但是各子項(xiàng)相對(duì)有序的數(shù)列。

復(fù)雜度：

時(shí)間復(fù)雜度為：O(nlogn) ——該算法最好、最壞和平均的時(shí)間性能。
空間復(fù)雜度為 ：O(n)
比較操作的次數(shù)介于(nlogn) / 2和 nlogn - n + 1之間。
賦值操作的次數(shù)是(2nlogn)。歸并算法的空間復(fù)雜度為：0 (n)
很難用于主存排序（歸并排序比較占用內(nèi)存，主要問(wèn)題在于合并兩個(gè)排序的表需要線性附加內(nèi)存，在整個(gè)算法中還要花費(fèi)將數(shù)據(jù)拷貝到臨時(shí)數(shù)組再拷貝回來(lái)這樣的一些附加操作，其結(jié)果嚴(yán)重放慢了排序的速度）但是效率很高，主要用于外部排序，對(duì)于重要的內(nèi)部排序應(yīng)用而言，一般還是選擇快速排序。

歸并操作的步驟如下：

第一步：申請(qǐng)空間，使其大小為兩個(gè)已經(jīng)排序序列之和，該空間用來(lái)存放合并后的序列
第二步：設(shè)定兩個(gè)指針，最初位置分別為兩個(gè)已經(jīng)排序序列的起始位置
第三步：比較兩個(gè)指針?biāo)赶虻脑兀x擇相對(duì)小的元素放入到合并空間，并移動(dòng)指針到下一位置
重復(fù)步驟3直到某一指針達(dá)到序列尾
將另一序列剩下的所有元素直接復(fù)制到合并序列尾

歸并排序的步驟如下（假設(shè)序列共有n個(gè)元素）：

將序列每相鄰兩個(gè)數(shù)字進(jìn)行歸并操作（merge)，形成floor(n/2)個(gè)序列，排序后每個(gè)序列包含兩個(gè)元素
將上述序列再次歸并，形成floor(n/4)個(gè)序列，每個(gè)序列包含四個(gè)元素
重復(fù)步驟2，直到所有元素排序完畢

更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題：《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點(diǎn)技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》

希望本文所述對(duì)大家java程序設(shè)計(jì)有所幫助。

最新評(píng)論