网站建网站建设,如何建设局域网内部网站,深圳个人网站设计,编程一个最简单游戏代码参考
左程云算法 算法导论
前言
本篇介绍
归并排序分治法
前置知识
了解递归#xff0c; 了解数组。
引入
归并排序 归并排序最早是由公认的现代计算机之父John von Neumann发明的#xff0c; 这是一种典型的分治思想应用。
我们先介绍分治思想 分治思想 分治思想的…参考
左程云算法 算法导论
前言
本篇介绍
归并排序分治法
前置知识
了解递归 了解数组。
引入
归并排序 归并排序最早是由公认的现代计算机之父John von Neumann发明的 这是一种典型的分治思想应用。
我们先介绍分治思想 分治思想 分治思想的想法基于递归 许多算法可以通过自身调用 来降低问题的规模 又获得与原问题类似的子问题。可见 分治法本质是递归思想的一个分支分治法还要额外进行处理 先进行递归地求解子问题 然后合并这些子问题的解求出原问题的解。
通过一个简单的例子 来讲解分治思想。 给定一个int类型的数组 求解该数组的最大值。 你可能已经很熟悉了 线性遍历即可。
public static int getMaxValue1(int[] arr) {int n arr.length;//max初始默认为系统最小值。int max Integer.MIN_VALUE;//无序数组 直接遍历for(int i0;in;i) {max Math.max(max, arr[i]);}return max;}分治思想如何运用呢 原数组区间范围在[0, arr.length - 1],求解原数组的大小可以被递归解决吗 很有可能的想法 直观上 我们求解原数组的最大值就是求解在原数组序列中最大值。只需要等分序列即可 将原数组序列的最大值分解成左右子序列的最大值问题 从递归上对子序列可以同样这样处理直到不需要递归继续降解规模了递归模式结束 处理基线条件以防止死递归了。 问题在于 规模确实减小了但左序列的最大值不一定是整个数组的最大值。 直觉上 将左右序列的最大值进行比较决定合并两个序列的最大值。 为此 我们可以写出分治法的求解子问题的写法。
public static int getMaxValue(int[] arr) {if(arrnull||arr.length0) {return Integer.MIN_VALUE;//处理值为null传参为空数组的情况。}return process(arr, 0, arr.length-1);}public static int process(int[] arr, int l, int r) {if(lr) {return Integer.MIN_VALUE;}if(lr) {return arr[l];//直接返回值}//递归条件 降低规模//分治的过程int mid (lr)/2;int lmax process(arr, l, mid);int rmax process(arr, mid1, r);//合并的过程。return Math.max(lmax, rmax);}public static void main(String[] args) {int[] arr {3,5,1,7,8,9,11,2};//对比两种方法 观察结果是否一致。 相互验证System.out.println(最大值:getMaxValue1(arr));System.out.println(最大值: getMaxValue(arr));}
/*** output:* 最大值:11* 最大值:11*/总结 对于每层递归 分治法有三个步骤
分解原问题为若干子问题不一定像上述例子二等分 子问题是规模减小的原问题。递归地处理这些子问题 核心是什么时候继续递归分解 什么时候直接求解。—写递归时必须想明白 否则StackOverflow等着你。合并处理子问题的解进而求出原问题的解。
能不能降低规模 处理好递归以及合并这个操作具体怎么写。写好分治法的难点。
归并排序
归并排序也是一种分治思想的体现。 基本思想就是左边有序右边有序。然后调整为整体有序。
分割 将数组序列二等分 利用递归不断分解。合并: 合并两个有序序列保持原来的元素的相对顺序不变。
结合代码和下面图片 public static void mergeSort(int[] arr) {//无效值null, 数组元素不为2不需要排序。if(arrnull || arr.length2) {return ;}//开始process(arr,0, arr.length-1);}public static void process(int[] arr, int l, int r) {//基线条件处理if(lr) {return ;}//选中分割下标 直接取中值即可int mid (lr)/2;//左边递归调用process(arr,l, mid);//右边递归调用 注意参数process(arr,mid1,r);//合并操作merge(arr,l,mid,r);}public static void merge(int[] arr,int l,int m, int r) {int i 0;int a l;int b m1;//拷贝一个临时数组int[] help new int[r-l1];//比大小的过程while(am br ) {help[i]arr[a]arr[b]?arr[a]:arr[b];}//处理剩余的序列while(am) {help[i] arr[a];}while(br) {help[i] arr[b];}//将数据拷贝回原序列。for(il;ir;i) {arr[i] help[i-l];}}//测试用例。public static void main(String[] args) {int[] arr {4,1,6,23,8,9,11,0,2,3,4,4,4,4,10};System.out.println(排序前:Arrays.toString(arr));mergeSort(arr);System.out.println(排序后Arrays.toString(arr));}/*** output* 排序前:[4, 1, 6, 23, 8, 9, 11, 0, 2, 3, 4, 4, 4, 4, 10]* 排序后[0, 1, 2, 3, 4, 4, 4, 4, 4, 6, 8, 9, 10, 11, 23]*/开始有一个主方法mergeSort只需要传递一个int数组即可。 process这一函数是不断递归地分解问题。merge函数是服务当前的process函数。 比如[4,8],[5,7]给定两个子序列 通过分离双指针和临时数组help进行比较原理是拷贝完较小的数组然后拷贝完剩余的数组。 先将两个序列的比较结果拷贝进help数组help[4,5,7]此时还剩下一个元素8因为没有数可比了序列[5,7]的指针已经走到了尽头。只需要挨个检查将剩下的元素依次拷贝进help数组即可。 以上就是对这行代码的解释: //比大小的过程while(am br ) {help[i]arr[a]arr[b]?arr[a]:arr[b];}//处理剩余的序列while(am) {help[i] arr[a];}while(br) {help[i] arr[b];}最后 将临时数组help存储的有序序列依次拷贝回原数组的对应序列即可。注意这里是原数组进行修改。 //将数据拷贝回原序列。for(il;ir;i) {arr[i] help[i-l];}递归版的复杂度
时间复杂度: O ( n l o g n ) O(nlogn) O(nlogn), 系统压栈高度为logn,merge函数时间 O ( n ) O(n) O(n) 乘起来就是 O ( n l o g n ) O(nlogn) O(nlogn)。 空间复杂度: O ( n ) O(n) O(n) 借助了一个临时数组help.
非递归实现
public static void mergeSort(int[] arr) {int n arr.length;//step分组数 step为1说明左右区间各有一个数除非区间已经越界 则相应调整//先两两分组 再以4个为一组 8个为一组...直到单次分组已经超过数组总的元素个数就终止。for (int l, m, r, step 1; step n; step 1) {l 0;//后面就是讨论区间while (l n) {//确定区间的中间下标m l step - 1;//判断右边界是否存在if (m 1 n) {//无右侧 不用后续merge了。break;//不存在说明单层的归并排序结束。}//求右边界r Math.min(l (step 1) - 1, n - 1);//确定好了l,m,r的值进行合并merge(arr, l, m, r);//内层while循环进行调整l r 1;}}}public static void merge(int[] arr,int l, int m,int r) {int a l;int b m1;int[] help new int[r-l1];int i 0;while(am br) {help[i] arr[a]arr[b]?arr[a]:arr[b];}while(am) {help[i] arr[a];}while(br) {help[i] arr[b];}for(il;ir;i) {arr[i] help[i-l];}}//测试用例。public static void main(String[] args) {int[] arr {4,1,6,23,8,9,11,0,2,3,4,4,4,4,10};System.out.println(排序前:Arrays.toString(arr));mergeSort(arr);System.out.println(排序后Arrays.toString(arr));}/*** output* 排序前:[4, 1, 6, 23, 8, 9, 11, 0, 2, 3, 4, 4, 4, 4, 10]* 排序后[0, 1, 2, 3, 4, 4, 4, 4, 4, 6, 8, 9, 10, 11, 23]*/归并排序为什么如此高效 左神说过是因为比较排序中的比较次数没有浪费。 确实如此 比较排序可以抽象为决策树模型 比较次数最少就是 n l o g n nlogn nlogn, 而对于三大平方的‘傻瓜式’排序算法 因为浪费了比较次数导致时间复杂度变高了。
练习 //请用递归和非递归方法实现。//阐述一下归并排序的思想。public static void mergeSort(int[] nums) {/*write code here! */}你已经学会了归并排序了 快速试试吧!。
总结
本篇并不涉及算法的严格分析 因为算法导论一书中已经写好了严谨有力的证明算法导论第二章和第4章。 下次见
