hello，大家好，我依旧是你们熟悉的槿凉。这几天跟C站的小伙伴们互动的那是一个热火朝天，然后我发的一个动态也是出现了热评，真的是非常感谢各路大佬给予我衷心的建议，有了大家的支持，对我自己的编程学习无疑是莫大的帮助哈！好了，废话不多说，今天我们就来说说这个归并排序算法！（先附上一张我的动态热评图叭 嘿嘿还是有点激动的）
定义：归并排序的基本思想是首先将a[0……n-1]看成n个长度为1的有序表，将相邻的k个有序子表成对归并，得到n/k个长度为k的有序子表，然后将这些有序子表继续归并，最后得到一个长度为n的有序表。
看完是不是有些懵啦! 好，没有关系，这里举个例子大家就看的比较清晰了。
好了，这里了解到归并排序的用法我们来到程序中具体看一个例子：
这里我们定义一个数组arr[]，里面有八个元素：
packageyinghang; importjava.util.Arrays; publicclassmargesort { publicstaticvoidmain(String[] args) { intarr[] = {1,2,3,4,5,6,7,8};
我们先设计一个合并的方法：（这里的temp数组相当于一个中转站，就是把排序好的数组元素放在里面 最后在赋值给原数组arr[]）
//合并的方法publicstaticvoidmerge(intarr[],intleft,intmid ,intright,inttemp[]) { inti=left;//初始化i，左边有序序列的初始序列intj=mid+1;//初始化j，右边有序序列的初始序列intt=0;//指向temp数组的当前序列
我们依次合并左右子表：
//先把左边有序序列的数据按照规则填充到temp数组//直到左右两边的有序序列，有一边处理完毕为止while(i<=mid&&j<=right) { if(arr[i] <=arr[j]){ temp[t]=arr[i]; t++; i++; }else{ temp[t] =arr[j]; t++; j++; }
然后有的小伙伴就要问了，那如果数组里面的元素不是偶数的话，那多出来的元素怎么办？哎，这个问题问得好，那么我们继续还要设计一个方法来将剩余元素依次加到temp数组中：
//把有剩余数据的一边的数据依次全部填充到temp数组中while(i<=mid) { temp[t] =arr[i]; t++; i++; } while(j<=right){ temp[t] =arr[j]; t++; j++; }
那么接下来就是分+合的方法，就是依次排序好左右子表 然后放到temp数组中去：
//分+合的方法publicstaticvoidmergesort(intarr[],intleft,intright,inttemp[]) { if(left<right) { intmid= (left+right)/2;//中间索引mergesort(arr,left,mid,temp);//向左子表进行分解mergesort(arr,mid+1,right,temp);//右子表分解 } }
这里我们在主函数里进行我们的输出：
inttemp[] =newint[arr.length];//归并排序需要一个额外空间mergesort(arr,0,arr.length-1,temp); System.out.println("归并排序后="+Arrays.toString(arr));
看的出来，我们的方法是正确的！那么我们最后给出最终的源代码：
importjava.util.Arrays; publicclassmargesort { publicstaticvoidmain(String[] args) { intarr[] = {1,2,3,4,5,6,7,8}; inttemp[] =newint[arr.length];//归并排序需要一个额外空间mergesort(arr,0,arr.length-1,temp); System.out.println("归并排序后="+Arrays.toString(arr)); } //分+合的方法publicstaticvoidmergesort(intarr[],intleft,intright,inttemp[]) { if(left<right) { intmid= (left+right)/2;//中间索引mergesort(arr,left,mid,temp);//向左子表进行分解mergesort(arr,mid+1,right,temp);//右子表分解 } } //合并的方法publicstaticvoidmerge(intarr[],intleft,intmid ,intright,inttemp[]) { inti=left;//初始化i，左边有序序列的初始序列intj=mid+1;//初始化j，右边有序序列的初始序列intt=0;//指向temp数组的当前序列//先把左边有序序列的数据按照规则填充到temp数组//直到左右两边的有序序列，有一边处理完毕为止while(i<=mid&&j<=right) { if(arr[i] <=arr[j]){ temp[t]=arr[i]; t++; i++; }else{ temp[t] =arr[j]; t++; j++; } }//把有剩余数据的一边的数据依次全部填充到temp数组中while(i<=mid) { temp[t] =arr[i]; t++; i++; } while(j<=right){ temp[t] =arr[j]; t++; j++; } } }
