您现在的位置是:首页 > 正文

算法 -归并排序

2024-04-01 02:55:00阅读 3


归并介绍

1)整体是递归,左边排好序+右边排好序+merge让整体有序
2)让其整体有序的过程里用了排外序方法
3)利用master公式来求解时间复杂度
4)当然可以用非递归实现

归并排序复杂度

T(N) = 2* T(N/2) + O(N^1)

根据master公式可知时间复杂度为O(N* logN)

merge过程需要辅助数组,所以额外空间复杂度为O(N)

归并排序的实质是把比较行为变成了有序信息并传递,比O(N^2)的排序快

为什么归并排序要比冒泡等排序快?

直观的说,我们想想一下冒泡排序每次要把最左的元素从头到尾和最终位置之前的元素进行比较,才得到一个最大值。也就是这个这一遍所有的比较只是为了计算某一个位置的值。
而归并则更有效的利用了比较,每次比较 都可以得到更有用的信息进行局部的排序。

归并排序的实质是把比较行为变成了有序信息并传递,所以比O(N^2)的排序快

例题及变种:

[ 求数组小和-每个数右边有多少个数比他大 ]
[ 求数组中的逆序对数量 每个数右边有多少个数比他小 ]
[ 求数组中的大两倍数对数量 ]
[ 数组用递归和非递归方式排序 ]

eg1:

  public static int getSmallSum(int[] arr) {
        //notice: 边界条件判定
        if (arr==null || arr.length<2){
            return 0;
        }
        return process(arr, 0, arr.length - 1);
    }

    private static int process(int[] arr, int l, int r) {
        if (l == r) {
            return 0;
        }
        int m = l + ((r - l) >> 1);

        //notice: sum 不用传入进去。递归想最外一层,sum 等于左右两个子集计算好的结果,再加上左右子集merge过程出现的数据即可
        return process(arr, l, m)
                +
                process(arr, m + 1, r)
                +
                merge(arr, l, m, r);

    }

    private static int merge(int[] arr, int l, int m, int r) {
        int p1 = l;
        int p2 = m + 1;
        int sum = 0;
        int p3 = 0;
        int[] help = new int[r - l + 1];
        while (p1 <= m && p2 <= r) {
            sum = arr[p1] < arr[p2] ? arr[p1] * (r - m + 1) : 0;
            help[p3++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];

        }
        while (p1<=m){
            help[p3++]=arr[p1++];
        }
        while (p2<=r){
            help[p3++]=arr[p2++];
        }
        for (int i = 0; i < help.length; i++) {
            arr[l + i] = help[i++];
        }
        return sum;
    }

本周打卡记录

 第二周进度: 应刷 14 道,实刷 4道
 投入时间 5h+

[ 求数组小和-每个数右边有多少个数比他大 ] 打卡 2022-04-24
[ 求数组中的逆序对数量 每个数右边有多少个数比他小 ] 打卡 2022-04-24
[ 求数组中的大两倍数对数量 ] 打卡 2022-04-24
[ 327.区间和达标的子数组数量 ]
[ 数组用递归和非递归方式排序 ] 打卡 2022-04-22

网站文章

  • Java文件上传实现 热门推荐

    Java文件上传实现 热门推荐

    (1)准备好前台页面Upload.html 表单 action=上传文件后台接口 method=“post”enctype=“multipart/form-data” 文件输入框&lt;input t...

    2024-04-01 02:54:18
  • Abaqus之动力分析中的阻尼的设置

    Abaqus之动力分析中的阻尼的设置

    以下内容主要参考 -带你了解ABAQUS中如何定义各种阻尼,但有修改部分内容和细节。1. 阻尼的含义系统结构特征值和模态的求解是在无阻尼情况下得到的,而在动力学问题中,任意结构都应存在或大或小的阻尼,...

    2024-04-01 02:54:05
  • PyTorch搭建LSTM实现时间序列预测(负荷预测)

    PyTorch搭建LSTM实现时间序列预测(负荷预测)

    PyTorch搭建LSTM实现时间序列预测(负荷预测)

    2024-04-01 02:53:59
  • oh-my-zsh安装zsh-autosuggestions插件(国内镜像源)

    从github上克隆zsh-autosuggestions终端命令自动推荐插件不好使,使用如下命令可解决该问题 1. 下载插件到/.oh-my-zsh/custom目录中 git clone http...

    2024-04-01 02:53:20
  • Git

    Git

    Git是一个开源的分布式版本控制系统,用以有效、高速的处理从很小到非常大的项目版本管理。Windows下的Git请看这里:http://www.oschina.net/p/msysgitGit 是 Linux Torvalds 为了帮助管理 Linux 内核开发而开发的一个开放源码的版本控制软件。Torvalds 开始着手开发 Git 是为了作为一种过渡方案来替代 BitKeeper,...

    2024-04-01 02:53:09
  • java8 stream多字段排序

    很多情况下sql不好解决的多表查询,临时表分组,排序,尽量用java8新特性stream进行处理使用java8新特性,下面先来点基础的List<类> list; 代表某集合//返回 对象集合以类属性一...

    2024-04-01 02:52:29
  • 研发工作中感受颇深的一些著名定律

    在书中,我们经常能够看到这样那样的法则、定律。然而真正经历过这些事,回过头来进行深度思考的时候,才越来越觉的这些定律、法则的道理之处。下边简述了一些自己感悟比较深刻的定律,当然还有很多,不断学习,不断经历,不断感悟,不断成长吧。 一,在系统设计时,应该多思考“墨菲定律”: 1,任何事都没有表面看起来那么简单; 2,所有的事都会比你预计的时间长; 3,可能出错的事总会出错; ...

    2024-04-01 02:52:20
  • 2012-01-31 学习笔记

    1.   Comprehend V$PROCESS VIEW2.   Comprehend PSEUDO PROCESS3.   Comprehend Database Process and how to related Operation System Process4.   Comprehend V$SESSION and V$PROCESS of relation5

    2024-04-01 02:52:13
  • 二叉树从根节点到r所指节点之间的路径并输出算法【C/C++】

    二叉树从根节点到r所指节点之间的路径并输出算法【C/C++】

    二叉树从根节点到r所指节点之间的路径并输出算法

    2024-04-01 02:51:31
  • 安卓相关测试

    安卓相关测试

    环境准备:网易Mumu安卓模拟器,里面还有adb方便调试: http://mumu.163.com/baidu/adb: brew cask install android-platform-tools动态调试adb连接,mac下网易mumu端口是5555,windows下是7555windows下:adb connect 127.0.0.1:7555adb shell...

    2024-04-01 02:51:24