Java算法之归并排序举例详解在2025年04月17日, 09点38分15秒这个时间点进行了更新处理, 而本次内容的作者信息显示为。这篇文章主要是介绍了一些关于Java算法里面有提到归并排序的相关资料, 说它是属于那种递归排序算法的类型, 就是把一个数组分成更多更小的子数组, 然后对这些子数组进行递归地的排序, 接着再把这些已经排好序的子数组给合并起来变成一个有序的数组, 在文章里面使用了代码来介绍这些内容, 这个介绍的力度可以说是非常详细了, 如果是需要的朋友的话可以去参考一下相关内容。一、归并排序在进行递归过程探索的时候, 1.思路是怎么样子的呢?理想那个结果嘛, 它就等于那个成分拆分成开之后的子结果所表达的那个公式。快速排序整个数组变得有序这件事, 可以拆开来看, 它其实就是说其中的某个元素本身是有序的, 并且它左边的那个断开了的数组也是有序的, 加上它右边的那个断开了的数组也是有序的, 把这三点合起来, 就等于整个数组是完全有序的。归并排序整个数组呈现有序状态, 其原因可以拆分为左侧断开部分的数组是有序的, 同时右侧断开部分的数组也是有序的, 并且这两个已经具备有序特性的数组, 最终经过了有序的合并操作。2.搭建2.当处于最底层的时候, 针对那种数据对不上的特殊情况进行设计。还有就是在从最底层往上数一点的位置, 查验功能可以完成基础的排列顺序操作。在进行向上点击操作, 且所处的位置属于最底层这一情况下的时候, 对于有序数组执行有序合并的这个动作来说, 在最底层的层面上是能够完成两个元素相互之间的比较工作的, 紧接着再实施排序处理的步骤的。2.在完成了第三步的跳转操作之后, 我们要继续进行上面的搭建工作:先跳转去那些已经排好顺序的数组结果那儿去, 接着再把它们按着顺序一步一步往上合并, 以此维持回搭的那种有序状态。3.实质从最底层的那一个个单独的、顺序断开且内部有序的数组开始, 再一层一层地往上进行组合, 把它们合并成规模更大的、同样是顺序断开的有序数组, 接着继续这样合并下去, 直到所有的部分都汇聚在一起, 最终形成一个完整的、大范围的有序数组为止。4.实现public static void mergeSort(int[] array) {mergeSortFunc(array,0,array.length-1);}private static void mergeSortFunc(int[] array,int left,int right) {if(left right) return;int mid (leftright) / 2;mergeSortFunc(array,left,mid);mergeSortFunc(array,mid1,right);merge(array,left,right,mid);}private static void merge(int[] array, int left, int right, int mid) {int s1 left;int s2 mid1;int[] tmpArr new int[right-left1];int k 0;//证明两个区间 都同时有数据的while (s1 mid s2 right) {if(array[s2] array[s1]) {tmpArr[k] array[s2];}else {tmpArr[k] array[s1];}}while (s1 mid) {tmpArr[k] array[s1];}while (s2 right) {tmpArr[k] array[s2];}//tmpArr 里面一定是这个区间内有序的数据了for (int i 0; i tmpArr.length; i) {array[ileft] tmpArr[i];}}二、递归的调用栈, 其具体体现就在于它完整的执行过程。在函数递归的过程中, 当前被调用的那个函数内部正在执行进一步的调用动作, 而这些调用的形式参数不断地发生变化, 随着参数值一次次深入下去, 最终执行的还是函数自身, 也就是它自己本身:第一次调用函数的时候, 执行过程停下来等第二次调用完成, 第二次执行停着等第三次调用完了, 形参带着变化一层层重复地调用但是都不往下进行, 直到最后一次调用的形参满足条件不再继续往下调了, 先拿出结果然后开始往回走推了一把让上一层没做完的事情接着做完, 这就是递归里从前往后推到尽头再从后往前回收的步骤。2.递归的函数栈帧凡是任意一个函数调用这种情况, 都会被独立地开辟出一个新的叫做函数栈帧的东西, 这个东西里面会存放局部变量、函数的形参、返回地址以及寄存器值, 然后把它压入到调用栈里面去, 一直到执行这个函数的语句结束之后, 才从这个栈中弹出它:在递归调用的过程中, 函数栈帧是依次从前往后独立地压入到栈里面的, 一直往下进行递归, 直到形参所满足的条件发生了变化, 然后开始由最新调用的那个函数所在的栈帧往上弹出, 当开始往上弹出栈帧并且有执行完之后往回一层一层往下返的时候, 在那个方法内部有可能写的代码又是继续再去执行当前这一层的形参条件所对应的那一次函数递归调用, 因为形参数的变化可能会被设置成不相同的值, 这就可能会形成左右各不一样的分支情况, 这种情形也就即是二叉树的情况2.1递归函数的栈帧压弹在归并排序的二叉树递归调用过程中2.将两个有序数组合并的那个函数, 它的栈帧在创建和销毁的过程。在执行调用合并有序数列的函数的时候, 调用栈又会压入合并有序数组函数的栈帧, 这里存放有开辟的当前层数组元素个数大小的数组, 这个数组是非常量级的, 是需要进行计算的。此时总的占用空间为调用栈的空间log(n减去……)加上n乘以减去……, 由于合并有序数组函数的栈帧每次都是处在栈顶压入的, 而且函数里面并没有再调用其他的函数在它之上再压栈, 所以它每次在栈顶进来压栈完成之后, 就紧接着弹出栈的。三、归并排序的空间复杂度, 这一点是1。空间复杂度所计算的结果, 指的是在从开始执行到结束完成的整个时段里面, 程序运行时在任何单一时刻点上所出现的最大的、临时的内存占用数量。在从最下层的递归调用开始, 一层一层地往回返的过程当中, 递归函数所占用的栈空间正在逐渐变小。同时, 负责合并有序数组的那个函数的函数栈帧正在逐渐变大, 并且在这个函数里面所涉及的数组规模也是变得越来越大的状态:2.时间复杂度时间复杂度, 指的是算整个递归调用过程, 把执行的时间全都加起来, 我们不用跟着递归搜索的过程去时时累计总和, 直接站在总二叉树的角度, 一层一层地算所有时间的和就行, 在层层递进里面, 每一个树节点以及它下面的部分全执行完, 对应的就是该调用函数的全执行完, 因为递归调用语句(array,left,mid)都已经转成里面的函数节点内容来算了, 且调用中的去执行调用部分是常量级的已经不算, 以及if(left right)、int mid (left right) / 2也都是常量级的执行时间不算, 对应到的总时间就是计算所有函数节点里的merge(array,left,right,mid)合并有序数组的时间和, 每一层里所有函数节点的合并有序数组时间和都为n, 除了最后一层的函数节点进去就直接判断为没执行有序数组合并,一共有log(n)层, 所以时间复杂度为O(n*log(n))。总结关于Java算法之归并排序这篇文章就介绍到这了, 更多信息可以搜索我以前的文章, 也可以继续浏览下面的相关文章, 希望大家以后多多支持我谢谢。