归并排序（四）

import java.util.Arrays;
/**
 * 
 * @author Administrator
 *归并排序原理：对于给定的一组记录（假设共有n个记录），首先将每两个相邻的长度为1的子序列进行归并，得到
 *n/2（向上取整）个长度为2或者1的有序子序列，再将其两两归并，反复执行此过程，直到得到一个有序序列
 *关键的两步：1、划分半子表；2、合并半子表
 */
public class MergeSort {
	/**
	 * 
	 * @param arry  表示原始数组
	 * @param p		表示数组首元素下标
	 * @param q		表示数组平分取整的中间值
	 * @param r		表示数组尾元素的下标
	 */
	public static void merge(int arry[],int p,int q,int r){
		int i,j,k,n1,n2;	//n1,n2用来确定两个划分数组的大小
		n1 = q+1-p;	
		n2 = r-q;
		int[] L = new int[n1];
		int[] R = new int[n2];
		//根据划分规则，将原始数组平分为L，R
		for(i=0,k=p;i<n1;i++,k++){
			L[i] = arry[k];
		}
		for(i=0,k=q+1;i<n2;i++,k++){
			R[i] = arry[k];
		}
		
		//对两个数组按照一定的顺序进行合并。并将合并后的数据存入到原始的数组中，此处按照从小到大排序
		for(i=0,j=0,k=p;i<n1&&j<n2;k++){	//注意这里每次增长的只是原始数组，L和R数组的移动是在每次比较时候
			if(L[i]>R[j]){
				arry[k] = R[j];
				j++;	//移动
			}else {
				arry[k] =L[i];
				i++;	//移动
			}
				
		}
		//如果L、R中有数组为空，直接将另一个数组中的元素取出并放入到原始数组中
		while(i<n1){
			arry[k++] = L[i++];
		}
		while(j<n2){
			arry[k++] = R[j++];
		}
	}
	
	/**
	 * 
	 * @param arry 原始数组
	 * @param p		数组首元素下标
	 * @param r		数组尾元素下标
	 * 归并排序核心：先递归，再合并
	 */
	public static void mergeSort(int arry[],int p,int r){
		if(p<r){	//递归的终止条件，相当重要
		int q=(p+r)/2;
		mergeSort(arry, p, q);
		mergeSort(arry, q+1, r);
		merge(arry, p, q, r);
		}
	}

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int a[] ={0,9,8,7,6,5,4,3,2,1};
		mergeSort(a, 0, 9);
		System.out.println(Arrays.toString(a));
	}

}

运行结果：

[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]