前言

今天介紹一種Divide and Conquer的排序方法 - Merge Sort

Merge Sort，排序的方式就是將手上的撲克牌，分成兩堆，再對半分成兩堆，直到一張牌是一個單位的時候，再依照剛剛拆分的順序，將兩個單位(各一張牌，共兩張牌)合併回去，並且新組成的單位都會排序好數字大小，所以最後手上的牌都會排好順序。

• Divide and Conquer 就是將複雜問題分解成很多個簡單的問題，先解決所有的簡單的問題，再把所有簡單的問題的答案合起來作為複雜問題的答案。
  • Divide : 將n個數字分成兩個(n/2)的數列
  • Conquer : 排序兩個數列
  • Combine : 合併排序過的兩個數列組成一個新的有序數列

Merge Sort

將未排序的數列，拆分成兩個幾乎等長的數列，直到不能再拆分，再合併各組的數列。
合併的時候，就是把兩個已經排序過的數列，重組成一個新的有序數列，直到全部的數組成一個數列。

• 時間複雜度 : O(n logn)

實作:

public class Merge_Sort 
{
	public static void main (String args[])
	{
		int ex[] =  {52, 99, 31, 60, 7, 46, 53};
		
		// before sort
		PrintArray(ex); 
				
		System.out.println("--------------------");
		MergeSort(ex);
		        
		// after sort
		PrintArray(ex); 
	}

	public static void MergeSort(int arr[])
    {
		Separate(arr, arr.length);
    }
	
	public static void Separate(int arr[], int len)
    {
		// 拆分的陣列長度不會小於1
        if(len > 1)
		{
			int mid = (len + 1) / 2;
			
			int left[] =  new int [mid];
			int right[] =  new int [len - mid];
			
			for(int i = 0; i < mid; i++)
			{
				left[i] = arr[i];
			}
			
			for(int i = mid, j = 0; i < len; i++,j++)
			{
				right[j] = arr[i];
			}
			
			// Recursion
			Separate(left, left.length);
			Separate(right, right.length);
			
			//合併
			Merge(arr, left, right);
		}
		
    }
	
	public static void Merge(int arr[], int left[], int right[])
    {
		int i = 0, j = 0, k = 0; // left[]、right[]、arr[]的Index
		
		//重複比較left[]，right[]兩個陣列的排頭大小，把比較小的先存進arr陣列中
		while(i < left.length && j < right.length && k < left.length + right.length)
		{
			if(left[i] <= right[j])
			{
				arr[k] = left[i];
				i++;
			}
			else
			{
				arr[k] = right[j] ;
				j++;
			}
			k++;
		}
		
		//若某一個陣列先排完，將另一個陣列剩下的數字存進arr陣列中
		while( i < left.length)
		{
			arr[k] = left[i];
			i++;
			k++;
		}
		
		while( j < right.length)
		{
			arr[k] = right[j] ;
			j++;
			k++;
		}
    }
	
	public static void PrintArray(int arr[])
	{
		for(int i = 0; i < arr.length; i++)
	    {
			System.out.print(arr[i] + " ");
	    }
		System.out.println();
	}
}

輸出結果:

52 99 31 60 7 46 53 
--------------------
7 31 46 52 53 60 99 

註: 筆者習慣數列從左到右，值會由小到大