当前位置:

首页 > 编程开发 > Java中归并排序算法的原理是什么几怎么实现

Java中归并排序算法的原理是什么几怎么实现

一、基本思想归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(DivideandConquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。二、算法分析1、算法描述把长度为n的输入序列分成两个长度为n/2的子序列;对这两个子序列分别采用归并排序;将两个排序好的子序列合并成一个最终的排序序列。2、过程分析(1)、现在我们将拆分项[1](指数从0到0,两边都包括)和[28]指数从1到

本文目录

      一、基本思想

      归并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法(Divide and Conquer)的一个非常典型的应用。将已有序的子序列合并,得到完全有序的序列;即先使每个子序列有序,再使子序列段间有序。若将两个有序表合并成一个有序表,称为2-路归并。

      二、算法分析

      1、算法描述

      把长度为n的输入序列分成两个长度为n/2的子序列;对这两个子序列分别采用归并排序;将两个排序好的子序列合并成一个最终的排序序列。

      2、过程分析

      (1)、现在我们将拆分项 [1] (指数从 0 到 0,两边都包括) 和 [28] 指数从 1 到 1 ,两边都包括) 归并在一起。

      Java中归并排序算法的原理是什么几怎么实现

      (2)、因为 1 (左拆分) <= 28 (右拆分), 我们将 {rightPart} 拷进新的数组。

      Java中归并排序算法的原理是什么几怎么实现

      (3)、因为左拆分是空的,我们将 28 (右拆分)拷进新的数组。

      Java中归并排序算法的原理是什么几怎么实现

      (4)、我们将新数组中的元素拷贝回原来的数组中。

      Java中归并排序算法的原理是什么几怎么实现

      (5)、因为 3 (左拆分) <= 21 (右拆分), 我们将 {rightPart} 拷进新的数组。

      Java中归并排序算法的原理是什么几怎么实现

      (6)、因为左拆分是空的,我们将 21 (右拆分)拷进新的数组。

      Java中归并排序算法的原理是什么几怎么实现

      (7)、现在我们将拆分项 [1,28] (指数从 0 到 1,两边都包括) 和 [3,21] 指数从 2 到 3 ,两边都包括) 归并在一起。

      Java中归并排序算法的原理是什么几怎么实现

      (8)、因为 1 (左拆分) <= 3 (右拆分), 我们将 {rightPart} 拷进新的数组。

      Java中归并排序算法的原理是什么几怎么实现

      (9)、因为 28 (左拆分) > 3 (右拆分), 我们将 {rightPart} 拷进新的数组。

      Java中归并排序算法的原理是什么几怎么实现

      (10)、因为 28 (左拆分) > 21 (右拆分), 我们将 {rightPart} 拷进新的数组。

      Java中归并排序算法的原理是什么几怎么实现

      (11)、因为右拆分是空的,我们将28 (左拆分) 拷贝进新的数组。

      Java中归并排序算法的原理是什么几怎么实现

      (12)、我们将新数组中的元素拷贝回原来的数组中。

      Java中归并排序算法的原理是什么几怎么实现

      (13)、现在我们将拆分项 [11] (指数从 4 到 4,两边都包括) 和 [7] 指数从 5 到 5 ,两边都包括) 归并在一起。

      Java中归并排序算法的原理是什么几怎么实现

      (14)、因为 11 (左拆分) > 7 (右拆分), 我们将 {rightPart} 拷进新的数组。

      Java中归并排序算法的原理是什么几怎么实现

      (15)、因为右拆分是空的,我们将11 (左拆分) 拷贝进新的数组。

      Java中归并排序算法的原理是什么几怎么实现

      (16)、我们将新数组中的元素拷贝回原来的数组中。

      Java中归并排序算法的原理是什么几怎么实现

      (17)、以此类推

      (18)、因为 1 (左拆分) <= 6 (右拆分), 我们将 {rightPart} 拷进新的数组。

      Java中归并排序算法的原理是什么几怎么实现

      (19)、因为 3 (左拆分) <= 6 (右拆分), 我们将 {rightPart} 拷进新的数组。

      Java中归并排序算法的原理是什么几怎么实现

      (20)、因为 21 (左拆分) > 6 (右拆分), 我们将 {rightPart} 拷进新的数组。

      Java中归并排序算法的原理是什么几怎么实现

      (21)、因为 21 (左拆分) > 7 (右拆分), 我们将 {rightPart} 拷进新的数组。

      Java中归并排序算法的原理是什么几怎么实现

      (22)、以此类推,我们将新数组中的元素拷贝回原来的数组中。

      Java中归并排序算法的原理是什么几怎么实现

      3、动图演示

      Java中归并排序算法的原理是什么几怎么实现

      三、算法实现

      package com.algorithm.tenSortingAlgorithm;
      
      import java.util.Arrays;
      
      public class MergeSort {
          private static void mergeSort(int[] arr, int low, int high) {
              if (low < high) { //当子序列中只有一个元素时结束递归
                  int mid = (low + high) / 2; //划分子序列
                  mergeSort(arr, low, mid); //对左侧子序列进行递归排序
                  mergeSort(arr, mid + 1, high); //对右侧子序列进行递归排序
                  merge(arr, low, mid, high); //合并
              }
          }
      
          private static void merge(int[] arr, int low, int mid, int high) {
              int[] temp = new int[arr.length]; //辅助数组
              int k = 0, i = low, j = mid + 1; //i左边序列和j右边序列起始索引,k是存放指针
              while (i <= mid && j <= high) {
                  if (arr[i] <= arr[j]) {
                      temp[k++] = arr[i++];
                  } else {
                      temp[k++] = arr[j++];
                  }
              }
              //如果第一个序列未检测完,直接将后面所有元素加到合并的序列中
              while (i <= mid) {
                  temp[k++] = arr[i++];
              }
              //同上
              while (j <= high) {
                  temp[k++] = arr[j++];
              }
              //复制回原数组
              for (int t = 0; t < k; t++) {
                  arr[low + t] = temp[t];
              }
          }
      
          public static void main(String[] args) {
              int[] arr = {1,28,3,21,11,7,6,18};
              mergeSort(arr, 0, arr.length - 1);
              System.out.println(Arrays.toString(arr));
          }
      }
      本站声明:本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系bd@zhengruan.com
      作者最新文章
      编程开发 Java
      相关文章 更多
      Yandex官网入口及网页搜索使用方法
      Yandex官网入口及网页搜索使用方法

      Yandex官网入口是https://www.yondex.net/,该平台支持多语言切换、智能搜索匹配、虚拟键盘变更及实时翻译,提供地图、图片、新闻、购物等垂直服务,并具备账户同步、隐私管理、个性化首页和云存储等功能。

      Java单元测试入门:使用JUnit 5编写第一个测试用例
      Java单元测试入门:使用JUnit 5编写第一个测试用例

      面向初学者的JUnit 5实用入门指南。从测试概念、Maven依赖配置,到手把手编写首个单元测试用例及断言验证,助你掌握Java单元测试的核心流程。

      Java变量未初始化报错解析:局部变量与成员变量默认值差异
      Java变量未初始化报错解析:局部变量与成员变量默认值差异

      深入解析Java中局部变量未初始化编译报错与成员变量自动赋予默认值的机制差异,涵盖JVM内存分配、编译期确定性赋值检查与实际排查修复方案。

      Java获取当前时间并格式化输出:DateTimeFormatter与SimpleDateFormat
      Java获取当前时间并格式化输出:DateTimeFormatter与SimpleDateFormat

      详细讲解在Java中获取当前系统时间并进行格式化输出的两种核心方案:基于Java 8全新日期时间API的DateTimeFormatter与传统遗留的SimpleDateFormat,包含完整代码示例、线程安全机制对比及生产选型建议。

      Java中final与static final常量的定义及初始化规则
      Java中final与static final常量的定义及初始化规则

      深入解析Java中final变量与static final常量的定义、内存语义、初始化时机及合法赋值路径,涵盖编译期常量优化与实战避坑指南。

      Java抽象方法与接口方法的区别及选型建议
      Java抽象方法与接口方法的区别及选型建议

      深入对比Java中抽象类抽象方法与接口方法的语法演进、设计意图及运行期差异,并提供清晰的架构选型决策流程与实战范例。

      Java实现HTTP请求与JSON解析的完整代码示例
      Java实现HTTP请求与JSON解析的完整代码示例

      本文提供Java标准库HttpClient发起HTTP GET/POST请求并结合Jackson进行JSON数据反序列化与序列化的完整代码示例与工程实践指南。

      Java递归出现StackOverflowError的原因分析及栈空间优化方案
      Java递归出现StackOverflowError的原因分析及栈空间优化方案

      详细分析Java递归调用出现StackOverflowError的原因,结合代码说明线程栈、栈帧和递归深度之间的关系,并介绍终止条件排查、迭代改写、减少栈帧开销以及通过-Xss调整JVM栈空间的方法。

      Java空指针异常(NPE)的代码排查与修复实例
      Java空指针异常(NPE)的代码排查与修复实例

      针对Java中常见的NullPointerException(NPE),本文从堆栈日志定位、典型代码触发场景、具体修复代码对比到防御体系进行系统讲解,提供实用且易上手的排查与修复方案。

      selenium上传文件教程本地文件路径设置方法
      selenium上传文件教程本地文件路径设置方法

      深入解析Selenium处理文件上传的技术细节,涵盖标准HTML控件的路径直接注入法与非标准控件的系统级模拟方案,提供Windows与Linux环境下的路径设置最佳实践及常见异常排查。

      查看更多
      精品专题 更多
      装机必备
      装机必备

      正软商城装机必备专区,精选办公、浏览器、安全防护、影音播放、压缩解压、设计创作和系统工具等电脑常用正版软件,帮助用户快速完成新电脑软件配置。

      Windows
      Windows

      正软商城Windows软件专区,汇集适用于Windows电脑的办公、设计、安全防护、影音播放、开发工具和系统优化软件,提供软件介绍、系统要求、正版授权及购买下载服务。

      PDF教程
      PDF教程

      正软商城PDF教程频道提供PDF编辑、转换、合并、拆分、压缩及格式处理方法,同时介绍常用PDF软件和工具的使用技巧。

      Mac软件 更多
      讯飞智作 网页版
      讯飞智作 网页版
      Windows/ macOS/ Linux

      讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

      火山引擎 网页版
      火山引擎 网页版
      Windows/ macOS/ Linux

      火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

      Aperty macOS版
      Aperty macOS版
      macOS

      Aperty 是 Skylum 推出的 AI 人像修图软件,支持自然肤质修饰、瑕疵处理、面部与身体调整、预设及批量同步。

      WINDOWS 更多
      讯飞智作 网页版
      讯飞智作 网页版
      Windows/ macOS/ Linux

      讯飞智作是一款基于语音合成技术、虚拟人驱动技术与数字人形象声音构建能力的 AI 数字人音视频创作平台。

      火山引擎 网页版
      火山引擎 网页版
      Windows/ macOS/ Linux

      火山引擎是字节跳动旗下企业级云与AI服务平台。聚焦大模型核心能力,依托字节自研豆包多模态大模型,凭借火山方舟一站式平台,提供模型精调、推理部署、智能应用搭建等全链路服务,结合高性能AI算力,助力各行业快速落地大模型数字化与智能化应用。

      PixTV 网页版
      PixTV 网页版
      Windows

      PixTV 是一款在浏览器中使用的 AI 视觉内容创作平台,提供图片、视频、音频、文字生成、AI 分镜、局部重绘、提示词反推和无限画布等工具,适合短剧、漫剧、广告及社交媒体内容制作。