文章详情

短信预约-IT技能 免费直播动态提醒

请输入下面的图形验证码

提交验证

短信预约提醒成功

java中归并排序及Master公式是什么

2023-06-26 03:37

关注

java中归并排序及Master公式是什么,针对这个问题,这篇文章详细介绍了相对应的分析和解答,希望可以帮助更多想解决这个问题的小伙伴找到更简单易行的方法。

基本思想

归并排序采取分治的思想进行排序,借用一张图片说明一下

java中归并排序及Master公式是什么

将n个元素从中间切开,分成两部分。(左边可能比右边多1个数) 将步骤1分成的两部分,再分别进行递归分解。直到所有部分的元素个数都为1。 从最底层开始逐步合并两个排好序的数列。
优点在于,分治之后,合并排序的过程时间复杂度是O(N)(只需要扫描一遍就可以将两个有序的数组合并成一个有序数组)

实现

  public static void MergeSort(int[] arr,int l , int r) {        if (l == r || r < 0){            return;        }        int middle = l+(r-l)/2; //取中值,可以防止达到Integer.MaxValue 溢出        MergeSort(arr,l,middle);        MergeSort(arr,middle+1,r);        sort(arr,l,middle,r);    }        private static void sort(int[] arr, int l, int middle, int r) {        int[] temp = new int[arr.length];        System.arraycopy(arr, 0, temp, 0, arr.length);        int right_first = middle+1;        int tempIndex = l;        while (l <= middle && right_first <= r){            if (temp[tempIndex] < temp[right_first]){                arr[l++] = temp[tempIndex++];            }else {                arr[l++] = temp[right_first++];            }        }        while (tempIndex <= middle){            arr[l++] = temp[tempIndex++];        }        while (right_first <= r ){            arr[l++] = temp[right_first++];        }    }

对数器验证

我们可以写个对数器,使用暴力排序的方式验证我们的排序方法是否准确

   //生成1-100内随机数组   public static int[] getParamArrays(){        int[] result = new int[(int) (Math.random() * 100)];        //随机生成数        for (int i = 0; i < result.length; i++) {            result[i] = (int) (Math.random() * 100);        }        return result;    }    public static void main(String[] args){        for (int i = 0; i < 1000000; i++) {            int[] nums = getParamArrays();            int[] temp = nums;            MergeSort(nums,0,nums.length-1);            Arrays.sort(temp);            //通过自定义比较次数,对随机数组进行排序验证正确性            if (!nums.equals(temp)){                System.out.println("wrong");            }        }        System.out.println("end");    }

递归时间复杂度计算 Master 公式

形如
T(N) = a * T(N/b) + O(N^d)(其中的a、b、d都是常数)
的递归函数,可以直接通过Master公式来确定时间复杂度
如果 log(b,a) < d,复杂度为O(N^d)
如果 log(b,a) > d,复杂度为O(N^log(b,a))
如果 log(b,a) == d,复杂度为O(N^d * logN)
此公式适用于子递归规模相等的情况下

a表示递归的次数也就是生成的子问题数,b表示每次递归是原来的1/b之一个规模,O(N^d) 表示分解和合并所要花费的时间之和(除开递归的复杂度)
此处就是 T(N)= 2*T(N/2)+O(N^1) 适用于第三种情况 复杂度为 O(nlogn)

关于java中归并排序及Master公式是什么问题的解答就分享到这里了,希望以上内容可以对大家有一定的帮助,如果你还有很多疑惑没有解开,可以关注编程网行业资讯频道了解更多相关知识。

阅读原文内容投诉

免责声明:

① 本站未注明“稿件来源”的信息均来自网络整理。其文字、图片和音视频稿件的所属权归原作者所有。本站收集整理出于非商业性的教育和科研之目的,并不意味着本站赞同其观点或证实其内容的真实性。仅作为临时的测试数据,供内部测试之用。本站并未授权任何人以任何方式主动获取本站任何信息。

② 本站未注明“稿件来源”的临时测试数据将在测试完成后最终做删除处理。有问题或投稿请发送至: 邮箱/279061341@qq.com QQ/279061341

软考中级精品资料免费领

  • 历年真题答案解析
  • 备考技巧名师总结
  • 高频考点精准押题
  • 2024年上半年信息系统项目管理师第二批次真题及答案解析(完整版)

    难度     813人已做
    查看
  • 【考后总结】2024年5月26日信息系统项目管理师第2批次考情分析

    难度     354人已做
    查看
  • 【考后总结】2024年5月25日信息系统项目管理师第1批次考情分析

    难度     318人已做
    查看
  • 2024年上半年软考高项第一、二批次真题考点汇总(完整版)

    难度     435人已做
    查看
  • 2024年上半年系统架构设计师考试综合知识真题

    难度     224人已做
    查看

相关文章

发现更多好内容

猜你喜欢

AI推送时光机
位置:首页-资讯-后端开发
咦!没有更多了?去看看其它编程学习网 内容吧
首页课程
资料下载
问答资讯