Java排序算法之 —— 合并（归并）排序
package algorithm.sort;/** * 合并（归并）排序：按照分治模式，操作如下： * 分解：将n个元素分成各含n/2个元素的子序列 * 解决：用合并排序法对两个子序列递归排序 * 合并：合并两个已经排序的子序列已得到排序结果 * @author Administrator */public class MergeSort {/** * 合并排序的关键在于合并两个已经排好序的子序列 * a[from, mid],a[mid+a, end]已排好序，合并成已排序的数组代替a[from, end] * @param a * @param from * @param end * @param mid *///方法一：在过程中利用最大值作为哨兵值，来避免检查每个子序列是否为空//一旦两个子序列都出现这个哨兵值，说明所有的值都已经合并，复制回数组apublic void merge1(int[] a, int from, int mid, int end) {//左右数组，且每个数组长度+1，为了存放哨兵值int nl = mid - from + 1;int nr = end - mid;int[] left = new int[nl + 1];int[] right = new int[nr + 1];System.arraycopy(a, from, left, 0, nl);System.arraycopy(a, mid+1, right, 0, nr);//哨兵值left[nl] = Integer.MAX_VALUE;right[nr] = Integer.MAX_VALUE;int i = 0;//控制左边数组int j = 0;//控制右边数组//从左右两个临时数组中各取一个数比较，将较小的一个数复制回数组for (int k = from; k <= end; k++) {if (left[i] <= right[j]) { //哨兵值在这里得到体现，如果其中一个复制完，就会一直复制另外一个a[k] = left[i];i++;//接着下一个} else {a[k] = right[j];j++;}}}//方法二：不使用哨兵值，一旦其中的一个子序列所有元素都被复制回数组a，就立刻停止//再将另外一个子序列中剩余的元素复制回数组a即可public void merge2(int[] a, int from, int mid, int end) {//左右数组int nl = mid - from + 1;int nr = end - mid;int[] left = new int[nl];int[] right = new int[nr];System.arraycopy(a, from, left, 0, nl);System.arraycopy(a, mid+1, right, 0, nr);int i=0, j=0, k=from;//一旦其中一个子序列所有元素复制完就立刻停止while(i < nl & j < nr) {if(left[i] <= right[j]) {a[k++] = left[i++];} else {a[k++] = right[j++];}}//复制剩余的元素for(; i < nl; i++){a[k++] = left[i];}for(; j < nr; j++) {a[k++] = right[j];}}//递归划分数组public void mergeSort(int[] a, int from, int end) {//单个元素视为已排好序的if(from < end) {//从中间划分数组int mid = (end + from) / 2;//递归划分数组mergeSort(a, from, mid);mergeSort(a, mid+1, end);merge2(a, from, mid, end);}}//对整个数组排序public void mergeSort(int[] a) {mergeSort(a, 0, a.length-1);}//打印数组public void printArr(String str, int[] a) {System.out.print(str + "\t");for(int i = 0; i < a.length; i++)System.out.print(a[i] + " ");System.out.println();}//测试数据public static void main(String[] args) {MergeSort ms = new MergeSort();int[] a = {1,4,3,7,5,8,0};ms.printArr("原始数组为：", a);ms.mergeSort(a);ms.printArr("合并排序后：", a);}}