歸并排序的原理及java代碼實現

更新時間：2016年02月02日 10:54:33 投稿：hebedich

歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。遞歸形式的算法在形式上較簡潔，但實用性很差。一般情況下，很少利用二路歸并排序法進行內部排序。

概述

歸并（Merge）排序法是將兩個（或兩個以上）有序表合并成一個新的有序表，即把待排序序列分為若干個子序列，每個子序列是有序的。然后再把有序子序列合并為整體有序序列。

歸并排序采用的是遞歸來實現，屬于“分而治之”，將目標數組從中間一分為二，之后分別對這兩個數組進行排序，排序完畢之后再將排好序的兩個數組“歸并”到一起，歸并排序最重要的也就是這個“歸并”的過程，歸并的過程中需要額外的跟需要歸并的兩個數組長度一致的空間。

效果圖：

步驟

申請空間，使其大小為兩個已經排序序列之和，該空間用來存放合并后的序列
設定兩個指針，最初位置分別為兩個已經排序序列的起始位置
比較兩個指針所指向的元素，選擇相對小的元素放入到合并空間，并移動指針到下一位置
重復步驟3直到某一指針達到序列尾
將另一序列剩下的所有元素直接復制到合并序列尾
實例

原始數據：

3 5 2 6 2
歸并的前提是將數組分開，一分為二，再一分為二，分到不能再分，進行歸并。

第一輪分隔，索引2 ((0+4)/2=2) 為中間

[3 5 2] [6 2]

第二輪分隔，對[3 5 2]進行分隔

[3 5] [2] [6 2]

第三輪分隔，對[3 5]進行分隔

[3] [5] [2] [6 2]

合并[3] [5]

[3 5] [2] [6 2]

合并[3 5] [2]

[2 3 5] [6 2]

第四輪分隔，對[6 2]進行分隔

[2 3 5] [6] [2]

合并[6] [2]

[2 3 5] [2 6]

合并[2 3 5] [2 6]

[2 2 3 5 6]

代碼實現(Java)

package com.coder4j.main.arithmetic.sorting;

public class Merge {
  
  private static int mark = 0;

  /**
   * 歸并排序
   * 
   * @param array
   * @param low
   * @param high
   * @return
   */
  private static int[] sort(int[] array, int low, int high) {
    int mid = (low + high) / 2;
    if (low < high) {
      mark++;
      System.out.println("正在進行第" + mark + "次分隔，得到");
      System.out.println("[" + low + "-" + mid + "] [" + (mid + 1) + "-" + high + "]");
      // 左邊數組
      sort(array, low, mid);
      // 右邊數組
      sort(array, mid + 1, high);
      // 左右歸并
      merge(array, low, mid, high);
    }
    return array;
  }

  /**
   * 對數組進行歸并
   * 
   * @param array
   * @param low
   * @param mid
   * @param high
   */
  private static void merge(int[] array, int low, int mid, int high) {
    System.out.println("合并:[" + low + "-" + mid + "] 和 [" + (mid + 1) + "-" + high + "]");
    int[] temp = new int[high - low + 1];
    int i = low;// 左指針
    int j = mid + 1;// 右指針
    int k = 0;
    // 把較小的數先移到新數組中
    while (i <= mid && j <= high) {
      if (array[i] < array[j]) {
        temp[k++] = array[i++];
      } else {
        temp[k++] = array[j++];
      }
    }
    // 兩個數組之一可能存在剩余的元素
    // 把左邊剩余的數移入數組
    while (i <= mid) {
      temp[k++] = array[i++];
    }
    // 把右邊邊剩余的數移入數組
    while (j <= high) {
      temp[k++] = array[j++];
    }
    // 把新數組中的數覆蓋array數組
    for (int m = 0; m < temp.length; m++) {
      array[m + low] = temp[m];
    }
  }

  /**
   * 歸并排序
   * 
   * @param array
   * @return
   */
  public static int[] sort(int[] array) {
    return sort(array, 0, array.length - 1);
  }

  public static void main(String[] args) {
    int[] array = { 3, 5, 2, 6, 2 };
    int[] sorted = sort(array);
    System.out.println("最終結果");
    for (int i : sorted) {
      System.out.print(i + " ");
    }
  }
}

測試輸出結果：

正在進行第1次分隔，得到
[0-2] [3-4]
正在進行第2次分隔，得到
[0-1] [2-2]
正在進行第3次分隔，得到
[0-0] [1-1]
合并:[0-0] 和 [1-1]
合并:[0-1] 和 [2-2]
正在進行第4次分隔，得到
[3-3] [4-4]
合并:[3-3] 和 [4-4]
合并:[0-2] 和 [3-4]
最終結果
2 2 3 5 6

經測試，與實例中結果一致。

您可能感興趣的文章: