算法：分治法之歸并排序

一、歸并的思想

是分治算法的完美展現

步驟一：拆解算法

a.找出分解點，在此處是是中間點拆分，拆成左右倆個數組。

b.左、右倆個數組采用同樣的方式拆解，一直循環拆，直到拆到一個元素為止（因為一個元素本身就是有序的特性），

步驟二：合并算法（利用倆個有序的數組比較簡單合并的思路，進行合并）

二、代碼展示

package com.yan.algorithm.devide;

public class Merge {
	
	/**
	 * 合并算法，調用的前提條件是：
	 * 1.下标low -> mid 有序
	 * 2.下标 mid + 1 -> high 有序
	 */
	public static void mergeSort(int[] a, int low, int mid, int high) {
		int i = low, j = mid + 1;// 倆個子數組的活動遊标
		int[] b = new int[high - low + 1];// 輔助數組
		int k = 0;// 輔助數組下标

		while (i <= mid && j <= high) {// 将小的元素放入輔助數組
			if (a[i] <= a[j]) {
				b[k++] = a[i++];
			}
			if (a[i] > a[j]) {
				b[k++] = a[j++];
			}
		}

		while (i <= mid) {//将左邊數組中剩餘的 i->mid 中的資料放入輔助數組
			b[k++] = a[i++];
		}
		while (j <= high) {//将右邊數組中剩餘的 j->high 中的資料放入輔助數組
			b[k++] = a[j++];
		}
		
		for(int m = 0; m < b.length; m++) {
			a[low + m] = b[m];
		}
	}
	
	//拆分，調用合并算法
	public static void merge(int[] a, int low, int high) {
		if(low == high) {//一個元素是有序的，不需要排序
			return ;
		}
		int mid = (low + high) / 2;
		merge(a, low, mid);
		merge(a, mid + 1, high);
		mergeSort(a, low, mid, high);
	}
	
	public static void main(String[] args) {
		int[] a = {5, 2, 50, 1, 29, 45, 35};
		merge(a, 0, a.length - 1);
		
		for(int t : a) {
			System.out.println(t);
			
		}
	}

}