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

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

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

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

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

算法分析：

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

復(fù)雜度：

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

歸并操作的步驟如下：

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

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

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

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

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

最新評論