package mydata;

public class MyMergeSort {

	/**
	 * 
	 * 1.递归拆分
	 * 2.合并
	 * 归并排序 先将初始的序列表看成是n个长度为1的有序表 
	 * (1)定义指针i,指向第一个序列表的第一个元素
	 * (2)定义指针j，指向第二个序列表的第一个元素 
	 * (3)比较i,j指向的元素大小，若前者大，将后者插入到新表中 否则，把前者插入到后表中
	 * (4)直到取完第一个序列表或者第二个序列表为止
	 * 
	 * @param args
	 */
	
	public static void main(String[] args) {
		int[] data = { 20, 37, 49, 28 };
		int result[] = new int[data.length];
		result = chaifen(data,0,data.length-1,result);
		for(int i = 0;i<result.length;i++){
			System.out.print(result[i] + " ");
		}
	}
	//拆分
	public static int[] chaifen(int[] data,int start,int end,int[] result){
		
		int[] temp = new int[end+1];
		if(start == end){
			result[start] = data[start];
		}else{
			int mid = (start + end) / 2;
			chaifen(data,start,mid,temp);//左半部分递归调用
			chaifen(data,mid+1,end,temp);//右半部分递归调用
			hebing(temp,start,mid,end,result);//temp是你要合并的数组，然后将合并的数组放到result中
		}
		
		return result;
	}

	//合并
	private static void hebing(int[] temp, int start, int mid, int end,int[] result) {
		int start1 = start;
		int end1 = mid;
		int start2 = mid + 1;
		int end2 = end;
		int index = start;
		while(start1 <= end1 && start2 <= end2){
			if(temp[start1] < temp[start2]){
				result[index] = temp[start1];
				index++;
				start1++;
			}else{
				result[index] = temp[start2];
				index++;
				start2++;
			}
		}
		
		while(start1<=end1){
			result[index++] = temp[start1++];
		}
		
		while(start2<=end2){
			result[index++] = temp[start2++];
		}
	}

}

java实现归并算法,布布扣,bubuko.com

java实现归并算法