博客

/**
	 * @program: sort
	 * @author: peanut
	 * @create: 2020.9.5
	 * @description: 归并排序
	 * 归并排序就是利用递归和分治技术将数据序列化分为越来越小的半子表
	 * 再将半子表排序，最后用递归方法将排好序的半子表合并为越来越大的有序列表
	 **/
	
	public void sort(int[] args,int r,int m,int l) {
		int i,j,k,n1,n2;
		n1 = m-r+1;
		n2 = l-m;
		int[] L=new int[n1];
		int[] R=new int[n2];
		for(i=0,k=r;i<n2;i++,k++)
			L[i] = args[k];
		for(j=0,k=m+1;j<n2;j++,k++) 
			R[j] = args[k];
		for(i=0,j=0,k=r;i<n1&&j<n2;k++) {
			if(L[i]<R[j]) {
				args[k] = L[i];
				i++;
			}else {
				args[k] = R[j];
				j++;
			}
		}
		
		if(i<n1) {
			for(j=i;j<n1;j++) {
				args[k] = R[j];
			}
		}
		
		if(j<n2) {
			for(i=j;i<n2;i++) {
				args[k] = L[i];
			}
		}
	}
	
	public void mergeSort(int[] args,int r,int l) {
		if(r<l) {
			int m = (r+l)/2;
			mergeSort(args, r, m);
			mergeSort(args, m+1, l);
			sort(args,r,m,l);
		}
	}