网站卡片设计,酒店类网站开发的策略,反邪手机网站建设方案,网站开发商城归并思想
先拆分后合并 也就是分治#xff1b; 拆分合并思想具体讲解可以参考以下链接#xff1a; b站链接#xff1a;
点这里#xff1a;b站归并思想具体讲解
看代码
代码中的例子参考上图和下图
public class MergeSort {//一、拆分部分public static void split(i…归并思想
先拆分后合并 也就是分治 拆分合并思想具体讲解可以参考以下链接 b站链接
点这里b站归并思想具体讲解
看代码
代码中的例子参考上图和下图
public class MergeSort {//一、拆分部分public static void split(int[] arr,int left,int right,int[] temp){//递归拆分if (leftright){int mid(leftright)/2;//左递归分解split(arr, left, mid, temp);//右递归分解split(arr, mid1, right, temp);//合并merge(arr,left,right,mid,temp); //这么理解就像递归就是重复干一件事 你调用执行就可//上面 先左递归合并 再右递归合并}}//二、合并部分/*** param arr 要进行排序的初始数组* param left 左序列数组的初始索引* param right 右序列数组的初始索引* param mid 左序列和右序列的交接地方 中间索引*/public static void merge(int[] arr, int left, int right, int mid, int[] temp) {int i left;//初始化i作为左序列的初始索引int j mid 1;//初始化j作为右序列的初始索引 mid是向下取整得来的int index 0;//temp数组的当前索引//1.左右两边序列按照规则填充到temp数组 直到有一边处理完毕//循环条件 两边的数据均为处理完while (i mid j right) {if (arr[i] arr[j]) { //左元素右 就把左里面的首位填充到temptemp[index] arr[i];i;//i后移index;//index后移} else {//反之就填充右里面的首位temp[index] arr[j];j;index;}}//当while循环结束 就有其中一边先处理完毕//2.把另一边中剩下的的数据直接依次填充到temp数组//满足哪个就去哪个循环进行填充while (j right) {temp[index] arr[j];index;j;}while ((i mid)) {temp[index] arr[i];index;i;}//3.temp数组拷贝到arr中//只有最后一次拷贝是把整个temp拷贝到arr数组中 前几次都是拷贝temp中的一部分//因为前几次的合并没有占满temp数组index0;//temp索引归0int tempLeftleft;//System.out.println(tempLefttempLeft rightright);//第1次合并 tempLeft0,right1;//第2次合并 tempLeft2,right3;//第3次合并 tempLeft0,right3;//第4次合并 tempLeft4,right5;//第5次合并 tempLeft6,right7;//第6次合并 tempLeft4,right7;//第7次合并 tempLeft0,right7;//最后一次合并while (tempLeftright){arr[tempLeft]temp[index];tempLeft;index;}}//主方法public static void main(String[] args) {int[] arr new int[]{8, 4, 5, 7, 6, 2, 3, 9};int[] tempnew int[arr.length];split(arr,0, arr.length-1,temp);System.out.println(Arrays.toString(arr));}
}
