Java 資料結構 - 歸併排序

歸併排序是一種基於分治技術的排序技術。其最壞時間複雜度為 Ο(n log n)，是備受推崇的演算法之一。

歸併排序首先將陣列分成相等的兩半，然後以排序的方式合併它們。

演算法

歸併排序不斷將列表分成相等的兩半，直到無法再分割為止。根據定義，如果列表中只有一個元素，則該列表已排序。然後，歸併排序合併較小的已排序列表，同時保持新列表也已排序。

Step 1: if it is only one element in the list it is already sorted, return.
Step 2: divide the list recursively into two halves until it can no more be divided.
Step 3: merge the smaller lists into new list in sorted order.

示例

import java.util.Arrays;

public class MergeSort {
   int[] array = { 10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0 };   

   public void merge(int low, int mid, int high) {
      int l1, l2, i, b[] = new int[array.length];
      
      for(l1 = low, l2 = mid + 1, i = low; l1 <= mid && l2 <= high; i++) {
         if(array[l1] <= array[l2]) {
         b[i] = array[l1++];
      } else
         b[i] = array[l2++];
      }
       
      while(l1 <= mid) {
         b[i++] = array[l1++];
      }
      while(l2 <= high) { 
         b[i++] = array[l2++];
      }
         for(i = low; i <= high; i++) {
         array[i] = b[i];
      }
   }
   public void sort(int low, int high) {
      int mid;

      if(low < high) {
         mid = (low + high) / 2;
         sort(low, mid);
         sort(mid+1, high);
         merge(low, mid, high);
      } else { 
         return;
      }   
   }
   public static void main(String args[]) {
      MergeSort obj = new MergeSort();
      int max = obj.array.length-1;
      System.out.println("Contents of the array before sorting : ");
      System.out.println(Arrays.toString(obj.array));
      obj.sort(0, max);

      System.out.println("Contents of the array after sorting : ");
      System.out.println(Arrays.toString(obj.array));
   }
}

輸出

[10, 14, 19, 26, 27, 31, 33, 35, 42, 44, 0]
Contents of the array after sorting : 
[0, 10, 14, 19, 26, 27, 31, 33, 35, 42, 44]