归并排序

归并排序是建立在归并操作上的一种有效的算法。该算法是采用分治法的一个非常典型的应用归并排序是一种稳定的排序方法。

将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为二路归并，同理还有多路归并。

package org.mino.sort;

/**
 * 归并排序
 * @author DingJie
 */
public class MergeSort {
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] num = {45, 12, 11, 32, 56, 11, 8, 30, 3};
		int[] numTemp = new int[9];
		System.out.println("排序之前：");
		for (int i : num) {
			System.out.print(i + " ");
		}
		System.out.println("");
		num = mergesort(num, 0, num.length - 1, numTemp);
		System.out.println("排序之后：");
		for (int i : num) {
			System.out.print(i + " ");
		}

	}

	private static int[] mergesort(int[] num, int s, int t, int[] numTemp) {
		int m;
		if (s == t)
			numTemp[s] = num[s];
		else {
			int[] numInTemp = new int[t + 1];   //需要相同大小
			m = (s + t) / 2;
			mergesort(num, s, m, numInTemp);    //左递归调用,产生左边有续表，其中也会调用merg方法
			mergesort(num, m + 1, t, numInTemp);//右递归调用，产生右边有续表
			merg(numInTemp, s, m, t, numTemp);  //将两个有续表合并
		}
		return numTemp;
	}
	/**
	 * 合并有序表（该算法在严蔚敏数据结构中连接两个有续表思想是一致的）
	 */
	private static void merg(int[] num, int l, int m, int n, int[] numTemp) {
		int i, j, k;
		i = l;
		j = m + 1;
		k = l;
		while (i <= m && j <= n) {
			if (num[i] < num[j])
				numTemp[k++] = num[i++];
			else {
				numTemp[k++] = num[j++];
			}
		}
		while (i <= m) {
			numTemp[k++] = num[i++];
		}
		while (j <= n) {
			numTemp[k++] = num[j++];
		}
	}

}