java資料結構排序演算法（2）歸併排序

這篇文章主要介紹了java資料結構排序演算法之歸併排序,結合具體實例形式詳細分析了歸併排序的原理、實現技巧與相關注意事項,需要的朋友可以參考下

本文實例講述了java資料結構排序演算法之歸併排序。分享給大家供大家參考，具體如下：

在前面說的那幾種排序都是將一組記錄按關鍵字大小排成一個有序的序列，而歸併排序的思想是：基於合併，將兩個或兩個以上有序表合併成一個新的有序表

歸併排序演算法：假設初始序列含有n個記錄，首先將這n個記錄看成n個有序的子序列，每個子序列長度為1,然後兩兩歸併，得到n/2個長度為2（n為奇數的時候，最後一個序列的長度為1 ）的有序子序列。在此基礎上，再對長度為2的有序子序列進行亮亮歸併，得到若干個長度為4的有序子序列。如此重複，直到得到一個長度為n的有序序列為止。這種方法稱為是：2-路歸併排序（基本運算是將待排序列中相鄰的兩個有序子序列合併成一個有序序列）。

演算法實作程式碼如下：

package exp_sort;
public class MergeSort {
  /**
   * 相邻两个有序子序列的合并算法
   *
   * @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-路归并排序算法，递归实现
   *
   * @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");
  }
}

程式碼解釋：

歸併排序中一趟歸併要多次調用到2-路歸併演算法，一趟的歸併的時間複雜度是O(n)，合併兩個已經排好序的表的時間顯然是線性的，因為最多進行了n-1次比較，其中n是元素的總數。如果有多個數，即n不為1時，遞歸的將前半部分數據和後半部分數據各自歸併排序，得到排序後的兩部分數據，再合併到一起。

演算法分析：

該演算法是建立在歸併操作（也叫歸併演算法，指的是將兩個已經排序的序列合併成一個序列的操作）上的一種有效的排序演算法。這個演算法是採用分治法（pide and Conquer）的一個非常典型的應用，它將問題分成一些小的問題然後遞歸求解，而治的階段則是將分的階段解得的各個答案修補到一塊；分治是遞歸非常有力的用法。注意：與快速·排序和堆排序比較，歸併排序最大的特點是，它一種穩定的排序方法。速度僅次於快速排序，一般用於對總體無序，但是各子項相對有序的數列。

複雜度：

時間複雜度為：O(nlogn) ——演算法最好、最壞和平均的時間性能。
空間複雜度為 ：O(n)
比較運算的次數介於(nlogn) / 2和 nlogn - n + 1之間。
賦值運算的次數是(2nlogn)。歸併演算法的空間複雜度為：0 (n)
很難用於主存排序（歸併排序比較佔用內存，主要問題在於合併兩個排序的表需要線性附加內存，在整個演算法中還要花費將資料拷貝到臨時數組再拷貝回來這樣的一些附加操作，其結果嚴重放慢了排序的速度）但是效率很高，主要用於外部排序，對於重要的內部排序應用而言，一般還是選擇快速排序。

歸併操作的步驟如下：

#第一步：申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合併後的序列
第二步：設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
第三步：比較兩個指針所指向的元素，選擇相對小的元素放入到合併空間，並移動指標到下一位置
重複步驟3直到某一指標達到序列尾
將另一序列剩下的所有元素直接複製到合併序列尾

歸併排序的步驟如下（假設序列共有n個元素）：

將序列每相鄰兩個數字進行歸併運算（merge )，形成floor(n/2)個序列，排序後每個序列包含兩個元素
將上述序列再次歸併，形成floor(n/4)個序列，每個序列包含四個元素
重複步驟2，直到所有元素排序完畢

【相關推薦】

1. java資料結構排序演算法（1）樹形選擇排序

2. 詳解Java中選擇排序（Selection Sort_java）的實例教程

#3. java資料結構排序演算法（3）簡單選擇排序

##############################################################################################

4. java資料結構排序演算法（4）選擇排序

#

以上是java資料結構排序演算法（2）歸併排序的詳細內容。更多資訊請關注PHP中文網其他相關文章！