首页 > 编程语言 >Java 归并排序

Java 归并排序

时间:2023-09-04 11:13:26浏览次数:38  
标签:归并 Java arr int mid 数组 last 排序 first

思路

数组排序主要分为两个部分:划分数组和归并排序。

划分数组:

  1. 将待排序的无序数组分为左右两个部分,如果无序数组的起始元素下标为first,最后一个元素的下标为last,那么左右两部分之间的临界点下标mid=(first+last)/2,这两部分分别是arr[first … mid]和arr[mid+1 … last];

  2. 将上面得到的两部分数组继续按照步骤(1)进行划分,直到划分的数组长度为1。

归并排序:

  1. 申请空间,空间大小为两个已经排序数组之和,该空间用来存放合并后的数组;

  2. 设定两个指针,最初位置分别为两个已经排序数组的起始位置;

  3. 比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;

  4. 重复步骤(3)直到某一指针超出数组尾,将另一数组剩下的所有元素直接复制到合并数组尾。

代码

    public void mergeSort(int[] arr, int first, int last) {
        int mid;
        if (first < last) {
            mid = (first + last) / 2;
            mergeSort(arr, first, mid);
            mergeSort(arr, mid + 1, last);
            merge(arr, first, mid, last);
        }
    }

    private void merge(int[] arr, int first, int mid, int last) {
        int i, j;
        int[] temp = new int[arr.length];
        int left_first = first;
        int right_first = mid + 1;

        for (i = 0; left_first <= mid && right_first <= last; i++) {
            if (arr[left_first] <= arr[right_first]) {
                temp[i] = arr[left_first++];
            } else {
                temp[i] = arr[right_first++];
            }
        }
        if (left_first <= mid) {
            for (j = left_first; j <= mid; j++) {
                temp[i++] = arr[j];
            }
        }
        if (right_first <= last) {
            for (j = right_first; j <= last; j++) {
                temp[i++] = arr[j];
            }
        }
        for (j = 0; j < last - first + 1; j++) {
            arr[first + j] = temp[j];
        }
    }

标签:归并,Java,arr,int,mid,数组,last,排序,first
From: https://www.cnblogs.com/liu-im/p/17676401.html

相关文章

  • Java 堆排序
    思路从最后的非叶子节点开始,从后向前构建一个堆(大顶堆/小顶堆);即最后的非叶子节点和其下的叶子节点构成一个大顶堆,然后再找前面一个非叶子节点继续此时根节点是最大的数据,然后将根节点和最后一位进行交换交换后,排除最后一位最大值,再从根节点开始构建大顶堆重复2,3步骤代码......
  • 20230529 java.lang.reflect.InvocationHandler
    介绍java.lang.reflect.InvocationHandlerpublicinterfaceInvocationHandlerAPIpublicinvokeinvokeDefault调用接口的default方法......
  • 20230529 java.lang.reflect.AnnotatedElement
    介绍java.lang.reflect.AnnotatedElementpublicinterfaceAnnotatedElementAPIisAnnotationPresentgetAnnotationgetAnnotationsgetAnnotationsByTypegetDeclaredAnnotationgetDeclaredAnnotationsByTypegetDeclaredAnnotations......
  • maven-resources-production:webapi: java.lang.NegativeArraySizeException
    maven-resources-production:webapi:java.lang.NegativeArraySizeException打开项目启动时,发现报这个错误,基于此,我分析了一下,首先原本好好的项目突然这样子,首先查看代码更新的情况,发现代码并没有作任何变化。分析代码jar包的问题,首先mvnclean和mvninstall直接一起上。代码可......
  • java多线程爬取笔趣阁所有小说
    可以选择下载的数量,全部下载下来够呛,首先没那么大的盘新版本:https://wws.lanzous.com/iAEMoghsgeb密码:7vjzjar包:https://wws.lanzous.com/ilphyghsgcj密码:f38a <dependency><!--jsoupHTMLparserlibrary[url=home.php?mod=space&uid=402414]@[/url]htt......
  • 全开源风车im源码(前端uniapp可发布H5及app/后端java含视频搭建教程)
    互联网彻底改变了我们的沟通方式,电子邮件是迄今为止采用最快的通信形式。不到二十年前,还没有多少人听说过它。现在,我们中的许多人都用电子邮件而不是写信,甚至打电话给别人,世界各地的人们每天发送数十亿封电子邮件。源码:ms.jstxym.top但有时甚至电子邮件也不够快。您可能不知道您......
  • GraalVM 打包 Java ShellcodeLoader 为可执行文件
    GraalVM打包JavaShellcodeLoader为可执行文件url:https://app.yinxiang.com/fx/a6667249-7c5e-40dd-8bf6-e474fc844163title:GraalVM打包JavaShellcodeLoader为可执行文件date:2023-03-0212:37:26打包成Jar包先上项目地址:https://github.com/yzddmr6/Java-Sh......
  • Failed to start bean 'documentationPluginsBootstrapper'; nested exception is jav
    2023-09-0322:53:53.622WARN20788---[main]ConfigServletWebServerApplicationContext:Exceptionencounteredduringcontextinitialization-cancellingrefreshattempt:org.springframework.context.ApplicationContextException:Failedtostartbean......
  • Java泛型
    Java泛型1.泛型概述泛型的本质是为了参数化类型(即限制参数类型为我们指定泛型类型)如这样:给list集合指定类型String//比如给List集合指定一个泛型(String),那么存入List集合中的元素必须要是String类型List<String>list=newArrayList<String>();2.泛型的优点限制变量的类......
  • 【面试题精讲】Java Stream排序的实现方式
    首发博客地址系列文章地址如何使用JavaStream进行排序在Java中,使用Stream进行排序可以通过sorted()方法来实现。sorted()方法用于对Stream中的元素进行排序操作。具体实现如下:对基本类型元素的排序:使用sorted()方法对Stream进行排序,默认是按照自然顺序进行排序。例如,对......