八种基本排序问题 （第六篇 归并排序）图文详解

归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案"修补"在一起，即分而治之)

1.先把数组进行分开  ，直到元素个数为一个时  ，

 2.然后进行合并 ，合并时两个相邻的有序子序列合并为一个序列

3.合并出的临时数组再赋值给原数组   

package c06Sort;

import java.util.Arrays;
//归并
public class c06MergetSort {

	public static void main(String[] args) {
		int [] arr = {8,4,5,7,1,3,6,2,4,0,6};
		int [] temp =new int [arr.length];
		mergeSort(arr, 0, arr.length-1, temp);
		System.out.println(Arrays.toString(arr));
		
	}
	
	
	//分+合 的方法
	public static void mergeSort(int [] arr,int left, int right,int [] temp) {
		//先把数组分开
		if(left< right) {
			int mid = (left+right)/2;
			//向左递归分组  
			mergeSort(arr, left, mid, temp);
			mergeSort(arr, mid+1, right, temp);
		
			//分解完后 加入合并
		   Merge(arr, left, mid, right, temp);
		}
		
	}
	
   //合并的方法
	public static void Merge(int [] arr,int left,int mid, int right,int [] temp) {
		//参数意义 原数组 左下标 中间 右边  临时数组
		int i=left; //左边的有序序列开始索引
		int j=mid+1;  //右边的有序序列开始索引
		int t=0;   // 合并的临时数组的当前索引
		
		//第一 把左右有序序列按照他们的数据大小 排列到临时数组 ,直到一边的完成、
		while(i<= mid&& j<=right) {
			//判断两边数据大小
			if(arr[i]<= arr[j]) {
				temp[t++]=arr[i++];
			}
			else {
				temp[t++]=arr[j++];
			 }
		  }
		//第二  判断是那一边的没有全部进入临时数据，并按顺序放进去
		while(i<=mid) {
			//左边未完
			temp[t++]=arr[i++];
		}
		
		while(j<=right) {
			temp[t++]=arr[j++];
		}
		
		//第三 复制临时数据 
		//每次都是从出过来的left开始到right
		t = 0;  //临时数组的下标
		int templeft =left;
		while(templeft<=right) {
			arr[templeft++]=temp[t++];
		}
	}
	
	
}