import java.util.Arrays;public class Mergesort {public static void main(String[] args) {int arr[]={8,4,5,7,1,3,6,2};int temp[]=new int[arr.length];//归并排序需要一个额外空间mergeSort(arr,0,arr.length-1,temp);System.out.println("归并排序后="+ Arrays.toString(arr));}/*要先“分”，因为后面要“并”，所以也就是分成一个一个的怎么分 ，可以从中间切，然后分成2组，这样递归，直到分成都是一个一个的为什么merge写在mergeSort里面一起递归 这个很巧妙因为mergeSort递归很明显 从他最里面那层的mergeSort开始看它的merge最里面那层 也就是“分”完了的 然后在调用merge开始并 比如本题此时是八个数 两个两个并成一组再依次往外层merge 这样递归这样就能理解了*/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);//在mergeSort里面调用合并的方法}}/*并的思想：并就是每次把两个小组两个小组并起来，并完之后小的放前面大的放后面（最开始是肯定两个数两个数合并，因为一开始都是单个的数）那怎么达到这个效果呢？ 首先你要知道一点就是，每个小组肯定是小的在前面大的在后面所以就把前面那个小组的第一个数依次和后面那个小组的数比 假如比后者小 就直接放进temp数组里然后就继续第一个小组第二个和那个数比 比他小 继续放进temp 直到有比它大的才把第二组那个数放进去再拿第二组第二个跟第一组刚刚那个数比 这样比下去...*///合并的方法public static void merge(int[] arr,int left,int mid,int right,int[] temp){int i=left;//初始化i，左边有序序列的初始索引int j=mid+1;//初始化j，右边有序序列的初始索引int t=0;//指向temp数组的当前索引while(i<=mid && j<=right){if(arr[i]<=arr[j]){//如果左边那组的当前元素小于右边，那么就将左边那个元素填充到temptemp[t]=arr[i];t+=1;i+=1;}else{temp[t]=arr[j];//反之，将右边元素填充到tempt+=1;j+=1;}//把有剩余数据的一边的数据一次全部填充到tempwhile (i<=mid){temp[t]=arr[i];t+=1;i=+1;}while (j<=right){temp[t]=arr[j];t+=1;j=+1;}//将temp数组的元素全部拷贝到arr//注意：不是每次拷贝所有 因为是一层一层的 每次并完一层就拷贝一层到arr 所以每层arr中元素顺序都不一样的 因为比过大小了t=0;int tempLeft=left;while(tempLeft<=right){arr[tempLeft]=temp[t];t+=1;tempLeft+=1;}}}}