当前位置: 首页 > news >正文

Java之归并排序

归并排序

归并排序(Merge Sort)算法,使用的是分治思想。分治,顾名思义,就是分而治之,将一个大问题分解成小的子问题来解决。小的子问题解决了,大问题也就解决了。

核心源码: mergeSort(m->n) = merge(mergeSort(m->k),mergeSort(k+1->n));

算法思路:

​ 如果要排序一个数组,先把数组从中间分成前后两部分,然后对前后两部分分别排序,再将排好序的两部分合并在一起,这样整个数组就都有序了。具体见下图:

在这里插入图片描述

注意:分治思想跟递归思想很相似。分治是一种解决问题的处理思想,递归是一种编程技巧,这两者并不冲突,分治算法一般都是用递归来实现。

具体代码实现如下:

import java.util.Arrays;
import org.junit.Test;/*** 
* @ClassName: MergeSort
* @author shaoyb
* @date 2020年12月9日
* @Description: 归并排序
* 归并排序思路:
*	1、把长度为n的序列一分为二成两个子序列;2、对这两个子序列分别采用归并排序;3、将两个排序好的子序列合并成一个最终的排序序列。*/
public class MergeSort {/*** 归并排序算法实现* @param arr 需要排序的数组* @return 排序成功后新数组*/public int[] mergeSort(int[] arr){//1.确定递归终止条件if(arr.length < 2) {return arr;}//2.拆解数组成左右两部分int mid = arr.length/2;int[] left = Arrays.copyOfRange(arr,0,mid);int[] right = Arrays.copyOfRange(arr,mid,arr.length);//3.对拆解后两个数组进行合并return merge(mergeSort(left),mergeSort(right));}/*** 合并两个有序数组,并返回合并后的新数组* @param left* @param right*/public int[] merge(int[] left,int[] right) {//1.定义好新数组int[] newArray = new int[left.length + right.length];//2.往新数组中逐个添加元素int lIndex = 0;int rIndex = 0;for(int i = 0; i < newArray.length; i++) {if(lIndex >= left.length) {//左数组已经遍历完成newArray[i] = right[rIndex++];}else if(rIndex >= right.length) {//右数组已经遍历完成newArray[i] = left[lIndex++];}else if(left[lIndex] < right[rIndex]) {//左数组当前元素值小于右数组newArray[i] = left[lIndex++];}else {//右数组当前元素值小于左数组newArray[i] = right[rIndex++];}}return newArray;}@Testpublic void testMergeSort(){//1.定义数组int[] array = new int[] {5,2,6,9,0,3};System.out.println("排序前" + Arrays.toString(array));//2.归并排序array = mergeSort(array);System.out.println("排序后" + Arrays.toString(array));}	
}

相关文章:

Java之归并排序

归并排序 归并排序(Merge Sort)算法&#xff0c;使用的是分治思想。分治&#xff0c;顾名思义&#xff0c;就是分而治之&#xff0c;将一个大问题分解成小的子问题来解决。小的子问题解决了&#xff0c;大问题也就解决了。 核心源码: mergeSort(m->n) merge(mergeSort(m-&g…...

了解ChatGPT API

要了解如何使用 ChatGPT API&#xff0c;可以参考几个有用的资源和教程&#xff0c;这些资源能帮助你快速开始使用 API 进行项目开发。下面是一些推荐的资源&#xff1a; OpenAI 官方文档&#xff1a; 访问 OpenAI 的官方网站可以找到 ChatGPT API 的详细文档。这里包括了 API …...

EasyAnimate - 阿里开源视频生成项目,国产版Sora,高质量长视频生成 本地一键整合包下载

EasyAnimate是阿里云人工智能平台PAI自主研发的DiT-based视频生成框架&#xff0c;它提供了完整的高清长视频生成解决方案&#xff0c;包括视频数据预处理、VAE训练、DiT训练、模型推理和模型评测等。在预训练模型的基础上&#xff0c;EasyAnimate可通过少量图片的LoRA微调来改…...

7月23日JavaSE学习笔记

异常&#xff1a; 程序中一些程序处理不了的特殊情况 异常类 Exception 继承自 Throwable 类&#xff08;可抛出的&#xff09; Throwable继承树 Error&#xff1a;错误/事故&#xff0c;Java程序无法处理&#xff0c;如 OOM内存溢出错误、内存泄漏...会导出程序崩溃 常见的…...

Linux——DNS服务搭建

&#xff08;一&#xff09;搭建nginx 1.首先布置基本环境 要求能够ping通外网&#xff0c;有yum源 2.安装nginx yum -y install nginx 然后查看验证 3.修改网页配置文件 修改文件&#xff0c;任意编写内容&#xff0c;然后去物理机测试 &#xff08;二&#xff09;创建一…...

C#中的wpf基础

在WPF中&#xff0c;Grid 是一种非常强大的布局控件&#xff0c;用于创建网格布局。它允许你将界面划分为行和列&#xff0c;并将控件放置在这些行和列中。 以下是一些关键点和示例&#xff0c;帮助你理解 WPF 中的 Grid&#xff1a; 基本属性 RowDefinitions&#xff1a;定义…...

基于微信小程序+SpringBoot+Vue的刷题系统(带1w+文档)

基于微信小程序SpringBootVue的刷题系统(带1w文档) 基于微信小程序SpringBootVue的刷题系统(带1w文档) 本系统是将网络技术和现代的管理理念相结合&#xff0c;根据试题信息的特点进行重新分配、整合形成动态的、分类明确的信息资源&#xff0c;实现了刷题的自动化&#xff0c;…...

SSH -i的用法

缘起 今天使用ssh -i指定私钥时遇到以下错误&#xff1a; WARNING: UNPROTECTED PRIVATE KEY FILE! Permissions 0644 for /home/ken/.ssh/my.pem are too open. It is required that your private key files are NOT accessible by others. This private key will b…...

小白学习webgis的详细路线

推荐打开boss直聘搜索相关岗位&#xff0c;查看岗位要求&#xff0c;对症下药是最快的。 第一阶段&#xff1a;基础知识准备 计算机基础 操作系统&#xff1a;理解Windows、Linux或macOS等操作系统的基本操作&#xff0c;学会使用命令行界面。网络基础&#xff1a;掌握TCP/I…...

使用ChatGPT来撰写和润色学术论文的教程(含最新升级开通ChatGpt4教程)​​

现在有了ChatGPT4o更加方便了, 但次数太少了 想要增加次数可以考虑升级开桶ChatGpt4​​ &#xff08; OPENAI4 可以减2刀&#xff09; 一、引言 在学术研究中&#xff0c;撰写高质量的论文是一项重要的技能。本教程将介绍如何利用ChatGPT来辅助完成从论文构思到润色的全过程…...

常见的 HTTP 状态码分类及说明

HTTP 响应状态码&#xff08;HTTP status code&#xff09;&#xff0c;表示服务器对请求的处理结果。常见的 HTTP 状态码有以下几类&#xff1a; 1xx: 信息响应 (Informational Responses) 100 Continue: 请求已收到&#xff0c;客户端应继续发送请求的其余部分。101 Switch…...

Leetcode700.二叉搜索树中搜索具体值

二叉搜索树的定义&#xff1a; 一颗空树或者具有以下性质的二叉树&#xff1a; 若任意节点的左子树不空&#xff0c;则左子树上所有节点的值均小于它的根节点的值&#xff1b;若任意节点的右子树不空&#xff0c;则右子树上所有节点的值均大于它的根节点的值&#xff1b;任意节…...

自动导入unplugin-auto-import+unplugin-vue-components

文章介绍 接下来将会以Vite Vue3 TS的项目来举例实现 在我们进行项目开发时&#xff0c;无论是声明响应式数据使用的ref、reactive&#xff0c;或是各种生命周期&#xff0c;又或是computed、watch、watchEffect、provide-inject。这些都需要前置引入才能使用&#xff1a; …...

Conda修改包/虚拟环境储存目录

Conda修改包/虚拟环境储存目录 关键字样例 关键字 通过conda config --show [key]可以查看某个配置的值&#xff0c;[key]留空可以查看所有配置 其中&#xff1a; envs-dirs 存放虚拟环境的储存目录pkgs_dirs 包的目录 通过conda config --add [key] [value]可以为配置添加值…...

Live555源码阅读笔记:哈希表的实现(C++)

&#x1f601;博客主页&#x1f601;&#xff1a;&#x1f680;https://blog.csdn.net/wkd_007&#x1f680; &#x1f911;博客内容&#x1f911;&#xff1a;&#x1f36d;嵌入式开发、Linux、C语言、C、数据结构、音视频&#x1f36d; &#x1f923;本文内容&#x1f923;&a…...

警务平台app

智慧公安以大数据、云计算、人工智能、物联网和移动互联网技术为支撑&#xff0c;以“打、防、管、控”为目的&#xff0c;综合研判为核心&#xff0c;共享信息数据资源&#xff0c;融合业务功能&#xff0c;构建公安智慧大数据平台&#xff0c;实现公安信息数字化、网络化和智…...

Java代理模式详解

Java代理模式详解 概念 代理模式是一种设计模式&#xff0c;为其他对象提供一种代理以控制对这个对象的访问。在某些情况下&#xff0c;一个对象不适合或者不能直接引用另一个对象&#xff0c;而代理对象可以在客户端和目标对象之间起到中介的作用。在Java中&#xff0c;代理…...

docker centos镜像 npm安装包时报错“npm ERR! code ECONNRESET”

1.采用新的镜像地址 npm config set registry https://registry.npmmirror.com2.清理缓存 npm cache clean --force3.安装yarn npm install -g yarn4. 安装模块 在node_modules 同级目录执行下面命令&#xff1a; yarn add napi-build-utils env-paths express ejs cors …...

Angular中component和directive的区别?

在Angular中&#xff0c;Component和Directive都是重要的构建块&#xff0c;用于构建和组织应用程序的UI。然而&#xff0c;它们有不同的用途和特点。以下是Component和Directive的主要区别&#xff1a; Component&#xff08;组件&#xff09; 1、定义&#xff1a;Component…...

Unity 资源 之 Pop It 3D 解压玩具与双人AI游戏 Unity 资源包分享

精彩呈现&#xff1a;Pop It 3D 解压玩具与双人AI游戏 Unity 资源包分享 一、Pop It 3D 解压玩具的魅力二、双人游戏的互动乐趣三、Unity 游戏资源包的优势四、如何获取资源包 亲爱的游戏爱好者们&#xff0c;今天为大家带来一款令人兴奋的游戏资源——Pop It 3D 解压玩具双人带…...

HTML 语义化

目录 HTML 语义化HTML5 新特性HTML 语义化的好处语义化标签的使用场景最佳实践 HTML 语义化 HTML5 新特性 标准答案&#xff1a; 语义化标签&#xff1a; <header>&#xff1a;页头<nav>&#xff1a;导航<main>&#xff1a;主要内容<article>&#x…...

docker详细操作--未完待续

docker介绍 docker官网: Docker&#xff1a;加速容器应用程序开发 harbor官网&#xff1a;Harbor - Harbor 中文 使用docker加速器: Docker镜像极速下载服务 - 毫秒镜像 是什么 Docker 是一种开源的容器化平台&#xff0c;用于将应用程序及其依赖项&#xff08;如库、运行时环…...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

让AI看见世界:MCP协议与服务器的工作原理

让AI看见世界&#xff1a;MCP协议与服务器的工作原理 MCP&#xff08;Model Context Protocol&#xff09;是一种创新的通信协议&#xff0c;旨在让大型语言模型能够安全、高效地与外部资源进行交互。在AI技术快速发展的今天&#xff0c;MCP正成为连接AI与现实世界的重要桥梁。…...

(转)什么是DockerCompose?它有什么作用?

一、什么是DockerCompose? DockerCompose可以基于Compose文件帮我们快速的部署分布式应用&#xff0c;而无需手动一个个创建和运行容器。 Compose文件是一个文本文件&#xff0c;通过指令定义集群中的每个容器如何运行。 DockerCompose就是把DockerFile转换成指令去运行。 …...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

【无标题】路径问题的革命性重构:基于二维拓扑收缩色动力学模型的零点隧穿理论

路径问题的革命性重构&#xff1a;基于二维拓扑收缩色动力学模型的零点隧穿理论 一、传统路径模型的根本缺陷 在经典正方形路径问题中&#xff08;图1&#xff09;&#xff1a; mermaid graph LR A((A)) --- B((B)) B --- C((C)) C --- D((D)) D --- A A -.- C[无直接路径] B -…...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)

目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 &#xff08;1&#xff09;输入单引号 &#xff08;2&#xff09;万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...

通过MicroSip配置自己的freeswitch服务器进行调试记录

之前用docker安装的freeswitch的&#xff0c;启动是正常的&#xff0c; 但用下面的Microsip连接不上 主要原因有可能一下几个 1、通过下面命令可以看 [rootlocalhost default]# docker exec -it freeswitch fs_cli -x "sofia status profile internal"Name …...