归并排序Java版(图文并茂思路分析)

这篇具有很好参考价值的文章主要介绍了归并排序Java版(图文并茂思路分析)。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

归并排序

工作原理:

工作原理是将一个大问题分解成小问题,再将小问题分解成更小的。(乍一看就觉得是像一个递归)就像下图这样。然后不断的将其一份为二,分解成更小的排序。

我们设一个函数叫MergeSort(arr,l,r)意思就是将arr数组下标为[ l ,r ]之间的数进行排序。

那么就开始不断的调用自己,从而不断的将数组一分为二

int mid = ( l + r ) / 2;
MergeSort( arr, l , mid );
MergeSort( arr, mid+1 , r);

其次我们的递归出口应该就是在变化的参数l > r 的时候,由于没有什么返回值,直接return就好了

if (l >= r) return;

最后我们要将分开的数组重新组合起来,所以我们还需要一个函数,我们就叫它merge(arr,l,mid,r)吧,我们来思考一下如何将两个数组合并起来呢

我们先来看一个问题,怎么把ab两个数组合并成有序的?

很简单的思路,从左右遍各拿一个出来对比,把小的放进有序数组就好了。比如先把左边的1和右边的2拿出来对比,发现1小,便把1放入新数组。

然后再将未放入的2和左边的3对比,发现2小,把2放进新数组,以此类推...

所以回到我们的归并排序,我们怎么实现上面的思路呢?

首先我们要先复制一个数组出来,保证有一个数组作为参考,另一个作为上面所谓的新数组,把拿出来的值覆盖掉另一个即可。然后发现我们这只有一个数组啊,怎么变成两个数组呢 —> 用3个点将数组分为2段就好了

所以此时此刻,我们只需要将i和j拿出来进行对比,然后将小的覆盖到传进来的原数组即可(也就是把上图的第一行数组覆盖了)

优化前:

package com.sort;
import java.util.Arrays;
​
/**
 * @Author: 翰林猿
 * @Description: 归并排序
 **/
public class Merge {
    public Merge() {
    }
​
    public static <E extends Comparable<E>> void Mergesort(E[] arr, int l, int r) {
        if (l >= r) 
            return;
        int mid = l +(r - l) / 2;
        Mergesort(arr, l, mid);
        Mergesort(arr, mid + 1, r);
        Merge(arr, l, mid, r);
    }
​
    public static <E extends Comparable<E>> void Merge(E[] arr, int l, int mid, int r) {
        //先把数组复制一个
        E[] copyArr = Arrays.copyOfRange(arr, l, r+1);
        //用两个变量记住第一个下标l和中间的下标mid+1将数组一分为二
        int i = l;
        int j = mid + 1;
        //走一遍数组,每轮都为arr[k]赋值,arr[k]最后是拿来按顺序覆盖传进来的原数组arr的从而形成排序
        for (int k = l; k <= r; k++) {
            //判断一下i是否越界,如果越界了,说明左边数组遍历完毕
            // 就应当将临时数组的j处的值赋给arr[k](也就是直接将目前右边数组遍历到的值赋给arr[k])
            //但是由于有偏移,比如说l是3,mid是6,r是9,其实存在copyarr里的下标是0,3,6
            //所以我们要用j-l计算偏移过后的真正下标
            if (i > mid) {
                arr[k] = copyArr[j - l];
                j++;                                //为了再下一次循环就可以只遍历我们的另一个数组了
            } else if (j > r) {                      //如果是j下标越界了,说明右边数组遍历完毕,将左边目前遍历到的值返回
                arr[k] = copyArr[i - l];            //同上
                i++;
            } else if (copyArr[i - l].compareTo(copyArr[j - l]) <= 0) {        //说明两边都没有越界,对比i和j并将小的赋给k,然后i++
                arr[k] = copyArr[i - l];                                       //左边小,把左边赋给k
                i++;
            } else {                                                           //右边小,把右边赋给k
                arr[k] = copyArr[j - l];
                j++;
            }
        }
    }
​
    public static void main(String[] args) {
        Integer[] arr = {3, 2, 1, 4, 5};
        Merge.Mergesort(arr, 0, arr.length-1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}

优化思路:

很多人其实不知道如何去优化一个算法,在这里总结几个方向给大家看看,这里主要是指排序类的算法。

个人认为优化其实就是去考虑一些边界和极端现象及内存浪费造成的性能损耗

  • 极端有序情况优化:

    • 如果给出的序列本身就是一个有序的,如何让算法减少遍历的次数甚至跳过?

    • 如果给出的序列很短,造成序列已经有序的数字概率很大,如何让算法不再重新将已经有序的数字重新再排序造成的性能损耗?

    这两个其实本质差不多,都是解决序列本身就有序或者接近有序怎么办。

    这里考虑两个方案:

    1. 用 i f 语句在某处进行判断是否已经有序之类的,如果有序就不再遍历下去。比如说这样:

      //优化一下,如果左数组和右数组连接的中间那两个数字已经有序,说明没必要再遍历下去了
      if (arr[mid].compareTo(arr[mid + 1]) > 0) {        
                  Merge(arr, l, mid, r);
      }
    2. 当序列很短时,我们使用对于短数组来说更快的算法。比如说当数组小于15个时使用复杂度为O(n)的插入排序

      if (r - l <= 15) {
          Insert.InsertSortForMerge(arr, l, r);
          return;
      }
  • 内存浪费优化

    • 考虑一下我们的算法中间有没有反复创建新的空间,导致内存不断占用之类的?

      比如说我们在复制数组的时候,其实一直在反复调用,这种情况我们可以把它提到上一层去,然后将其当作一个参数传给下面调用者。这样无需在调用者种反复复制数组,完成内存操作优化。

到这里,其实我们的优化还没有完成,我们只是将一个arr这么大的数组空间重复利用了,但是内容还没有拷贝,我们可以使用这段代码将内容也拷贝进去。同时还顺便解决了偏移量的问题,不再需要老是减一个 L 了

System.arraycopy(arr, l, copyArr, l, r - l + 1);

优化后代码:

package com.sort;
import java.util.Arrays;
​
/**
 * @Author: 翰林猿
 * @Description: 归并排序
 **/
public class Merge {
    public Merge() {
    }
​
    public static <E extends Comparable<E>> void Mergesort(E[] arr, int l, int r) {
        //将copy出来的arr提到上一层来,这样不必反复copy数组,节约内存空间。
        E[] copyArr = Arrays.copyOf(arr, arr.length);
        if (r - l <= 15) {
            Insert.InsertSortForMerge(arr, l, r);
            return;
        }
        int mid = l + (r - l) / 2;
        Mergesort(arr, l, mid);
        Mergesort(arr, mid + 1, r);
        if (arr[mid].compareTo(arr[mid + 1]) > 0) {         //优化一下,如果左数组和右数组连接的中间那两个数字已经有序,说明没必要再遍历下去了
            Merge(arr, l, mid, r, copyArr);
        }
    }
​
    public static <E extends Comparable<E>> void Merge(E[] arr, int l, int mid, int r, E[] copyArr) {
        //先把数组复制一个
        //E[] copyArr = Arrays.copyOfRange(arr, l, r + 1);      优化到上面
        System.arraycopy(arr, l, copyArr, l, r - l + 1);
​
​
        //用两个变量记住第一个下标l和中间的下标mid+1将数组一分为二
        int i = l;
        int j = mid + 1;
        //走一遍数组,每轮都为arr[k]赋值,arr[k]最后是拿来按顺序覆盖传进来的原数组arr的从而形成排序
        for (int k = l; k <= r; k++) {
            //判断一下i是否越界,如果越界了,说明左边数组遍历完毕
            // 就应当将临时数组的j处的值赋给arr[k](也就是直接将目前右边数组遍历到的值赋给arr[k])
            //但是由于有偏移,比如说l是3,mid是6,r是9,其实存在copyarr里的下标是0,3,6
            //所以我们要用j-l计算偏移过后的真正下标
            if (i > mid) {
                arr[k] = copyArr[j];
                j++;                                //为了再下一次循环就可以只遍历我们的另一个数组了
            } else if (j > r) {                      //如果是j下标越界了,说明右边数组遍历完毕,将左边目前遍历到的值返回
                arr[k] = copyArr[i];            //同上
                i++;
            } else if (copyArr[i].compareTo(copyArr[j]) <= 0) {        //说明两边都没有越界,对比i和j并将小的赋给k,然后i++
                arr[k] = copyArr[i];                                       //左边小,把左边赋给k
                i++;
            } else {                                                           //右边小,把右边赋给k
                arr[k] = copyArr[j];
                j++;
            }
        }
    }
​
    public static void main(String[] args) {
        Integer[] arr = {3, 2, 1, 4, 5, 9, 19, 15, 18};
        Merge.Mergesort(arr, 0, arr.length - 1);
        for (int i = 0; i < arr.length; i++) {
            System.out.println(arr[i]);
        }
    }
}
​

 文章来源地址https://www.toymoban.com/news/detail-458540.html

 

 

 

 

到了这里,关于归并排序Java版(图文并茂思路分析)的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • Activiti7(图文并茂)

    Activiti 是由 jBPM (BPM,Business Process Management 即业务流程管理) 的创建者 Tom Baeyens 离开 JBoss 之后建立的项目,构建在开发 jBPM 版本 1 到 4 时积累的多年经验的基础之上,旨在创建下一代的 BPM 解 决方案。 Activiti 作为一个开源的工作流引擎,它实现了BPMN 2.0规范,可以发布设计

    2024年02月06日
    浏览(60)
  • RabbitMQ入门篇【图文并茂,超级详细】

    接下来看看由辉辉所写的关于RabbitMQ的相关操作吧 目录 🥳🥳Welcome 的Huihui\\\'s Code World ! !🥳🥳 前言 1.什么是MQ 2.理解MQ 3.生活案例分析与理解 4.MQ的使用场景 (1)解耦 传统模式 中间件模式 (2)削峰 传统模式 中间件模式 (3)异步  传统模式 中间件模式 5.常见的MQ 一. Rab

    2024年01月20日
    浏览(53)
  • secureCRT安装和使用教程【图文并茂】

    简介 一般而言,嵌入式开发板使用串口来监控后台。可以使用串口线连接开发板和电脑,对于没有串口的笔记本电脑来说,一般还需要一根USB转串口线。 串口线 串口软件多种多样,比如secureCRT、Xshell、超级终端、miniCom、putty等,它们的功能大同小异,因此只需安装用的顺手

    2024年02月03日
    浏览(94)
  • 发送图文并茂的html格式的邮件

    本文介绍如何生成和发送包含图表和表格的邮件,涉及echarts图表转换为图片、图片内嵌到html邮件内容中、html邮件内容生成、邮件发送方法等 因为html格式的邮件不支持echarts,也不支持js执行,所以图表需要转换为图片内嵌在邮件内容中 因为平台首页相关统计都是使用echarts渲

    2024年02月11日
    浏览(42)
  • 什么是感知机——图文并茂,由浅入深

    生活中常常伴随着各种各样的逻辑判断,比如看到远方天空中飘来乌云,打开手机看到天气预报说1小时后40%的概率下雨,此时时候我们常常会做出等会下雨,出门带伞的判断。 上述思考过程可以抽象为一个”与“的”神经逻辑“。当”看到乌云“和”天气预报40%下雨“同时

    2023年04月20日
    浏览(41)
  • Flutter 图文并茂:打造交互丰富的应用界面

    Flutter作为一种现代的UI工具包,为开发者提供了丰富的工具和小部件,轻松构建漂亮、响应迅速的应用界面。本篇博客将带你踏入Flutter的世界,学习如何巧妙运用图片、按钮、图标,以及行与列进行布局,打造令人惊艳的用户交互体验。 无论你是Flutter初学者还是有一定经验

    2024年02月03日
    浏览(42)
  • NodeMCU ESP8266开发流程详解(图文并茂)

    NodeMCU ESP8266基于Arduino IDE的开发相对来说还是比较容易上手的,我们基本需要以下几个东西; 一台安装好Arduino IDE的PC,并且已经部署环境(安装好开发板的串口驱动); NodeMCU ESP8266 开发板; USB线(根据实际开发板的情况,本文需要Micro-USB的线); 具体如下图所示; 本文默

    2024年02月06日
    浏览(57)
  • 最新阿里云服务器配置选择教程(图文并茂)

     很多第一次接触云服务器的新用户不知道怎么购买,每一步怎么操作,每个参数代表的是什么意思,怎么选择最好,那么下面这篇文章将详细介绍选购阿里云服务器的每个步骤,希望可以帮助到你! 进入阿里云官网:https://www.aliyun.com 点击立即注册 可以选择支付宝扫码登陆

    2024年02月02日
    浏览(52)
  • kali Linux 安装教程(绝对简单清晰,图文并茂)

    基于 Debian 的Linux操作系统   Kali Linux是基于 Debian 的 Linux发行版 , 设计用于数字取证操作系统。每一季度更新一次。由 Offensive Security Ltd 维护和资助。最先由Offensive Security的Mati Aharoni和Devon Kearns通过重写BackTrack来完成,BackTrack是他们之前写的用于取证的Linux发行版 。【百度

    2024年02月15日
    浏览(36)
  • Canvas鼠标滚轮缩放以及画布拖动(图文并茂版)

    本文会带大家认识Canvas中常用的坐标变换方法 translate 和 scale,并结合这两个方法,实现鼠标滚轮缩放以及画布拖动功能。 Canvas 绘图的缩放以及画布拖动主要通过 CanvasRenderingContext2D 提供的 translate 和 scale 两个方法实现的,先来认识下这两个方法。 translate 方法 语法: trans

    2023年04月09日
    浏览(52)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包