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)算法,使用的是分治思想。分治,顾名思义,就是分而治之,将一个大问题分解成小的子问题来解决。小的子问题解决了,大问题也就解决了。 核心源码: mergeSort(m->n) merge(mergeSort(m-&g…...
了解ChatGPT API
要了解如何使用 ChatGPT API,可以参考几个有用的资源和教程,这些资源能帮助你快速开始使用 API 进行项目开发。下面是一些推荐的资源: OpenAI 官方文档: 访问 OpenAI 的官方网站可以找到 ChatGPT API 的详细文档。这里包括了 API …...
EasyAnimate - 阿里开源视频生成项目,国产版Sora,高质量长视频生成 本地一键整合包下载
EasyAnimate是阿里云人工智能平台PAI自主研发的DiT-based视频生成框架,它提供了完整的高清长视频生成解决方案,包括视频数据预处理、VAE训练、DiT训练、模型推理和模型评测等。在预训练模型的基础上,EasyAnimate可通过少量图片的LoRA微调来改…...
7月23日JavaSE学习笔记
异常: 程序中一些程序处理不了的特殊情况 异常类 Exception 继承自 Throwable 类(可抛出的) Throwable继承树 Error:错误/事故,Java程序无法处理,如 OOM内存溢出错误、内存泄漏...会导出程序崩溃 常见的…...
Linux——DNS服务搭建
(一)搭建nginx 1.首先布置基本环境 要求能够ping通外网,有yum源 2.安装nginx yum -y install nginx 然后查看验证 3.修改网页配置文件 修改文件,任意编写内容,然后去物理机测试 (二)创建一…...
C#中的wpf基础
在WPF中,Grid 是一种非常强大的布局控件,用于创建网格布局。它允许你将界面划分为行和列,并将控件放置在这些行和列中。 以下是一些关键点和示例,帮助你理解 WPF 中的 Grid: 基本属性 RowDefinitions:定义…...
基于微信小程序+SpringBoot+Vue的刷题系统(带1w+文档)
基于微信小程序SpringBootVue的刷题系统(带1w文档) 基于微信小程序SpringBootVue的刷题系统(带1w文档) 本系统是将网络技术和现代的管理理念相结合,根据试题信息的特点进行重新分配、整合形成动态的、分类明确的信息资源,实现了刷题的自动化,…...
SSH -i的用法
缘起 今天使用ssh -i指定私钥时遇到以下错误: 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直聘搜索相关岗位,查看岗位要求,对症下药是最快的。 第一阶段:基础知识准备 计算机基础 操作系统:理解Windows、Linux或macOS等操作系统的基本操作,学会使用命令行界面。网络基础:掌握TCP/I…...
使用ChatGPT来撰写和润色学术论文的教程(含最新升级开通ChatGpt4教程)
现在有了ChatGPT4o更加方便了, 但次数太少了 想要增加次数可以考虑升级开桶ChatGpt4 ( OPENAI4 可以减2刀) 一、引言 在学术研究中,撰写高质量的论文是一项重要的技能。本教程将介绍如何利用ChatGPT来辅助完成从论文构思到润色的全过程…...
常见的 HTTP 状态码分类及说明
HTTP 响应状态码(HTTP status code),表示服务器对请求的处理结果。常见的 HTTP 状态码有以下几类: 1xx: 信息响应 (Informational Responses) 100 Continue: 请求已收到,客户端应继续发送请求的其余部分。101 Switch…...
Leetcode700.二叉搜索树中搜索具体值
二叉搜索树的定义: 一颗空树或者具有以下性质的二叉树: 若任意节点的左子树不空,则左子树上所有节点的值均小于它的根节点的值;若任意节点的右子树不空,则右子树上所有节点的值均大于它的根节点的值;任意节…...
自动导入unplugin-auto-import+unplugin-vue-components
文章介绍 接下来将会以Vite Vue3 TS的项目来举例实现 在我们进行项目开发时,无论是声明响应式数据使用的ref、reactive,或是各种生命周期,又或是computed、watch、watchEffect、provide-inject。这些都需要前置引入才能使用: …...
Conda修改包/虚拟环境储存目录
Conda修改包/虚拟环境储存目录 关键字样例 关键字 通过conda config --show [key]可以查看某个配置的值,[key]留空可以查看所有配置 其中: envs-dirs 存放虚拟环境的储存目录pkgs_dirs 包的目录 通过conda config --add [key] [value]可以为配置添加值…...
Live555源码阅读笔记:哈希表的实现(C++)
😁博客主页😁:🚀https://blog.csdn.net/wkd_007🚀 🤑博客内容🤑:🍭嵌入式开发、Linux、C语言、C、数据结构、音视频🍭 🤣本文内容🤣&a…...
警务平台app
智慧公安以大数据、云计算、人工智能、物联网和移动互联网技术为支撑,以“打、防、管、控”为目的,综合研判为核心,共享信息数据资源,融合业务功能,构建公安智慧大数据平台,实现公安信息数字化、网络化和智…...
Java代理模式详解
Java代理模式详解 概念 代理模式是一种设计模式,为其他对象提供一种代理以控制对这个对象的访问。在某些情况下,一个对象不适合或者不能直接引用另一个对象,而代理对象可以在客户端和目标对象之间起到中介的作用。在Java中,代理…...
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 同级目录执行下面命令: yarn add napi-build-utils env-paths express ejs cors …...
Angular中component和directive的区别?
在Angular中,Component和Directive都是重要的构建块,用于构建和组织应用程序的UI。然而,它们有不同的用途和特点。以下是Component和Directive的主要区别: Component(组件) 1、定义:Component…...
Unity 资源 之 Pop It 3D 解压玩具与双人AI游戏 Unity 资源包分享
精彩呈现:Pop It 3D 解压玩具与双人AI游戏 Unity 资源包分享 一、Pop It 3D 解压玩具的魅力二、双人游戏的互动乐趣三、Unity 游戏资源包的优势四、如何获取资源包 亲爱的游戏爱好者们,今天为大家带来一款令人兴奋的游戏资源——Pop It 3D 解压玩具双人带…...
观成科技:隐蔽隧道工具Ligolo-ng加密流量分析
1.工具介绍 Ligolo-ng是一款由go编写的高效隧道工具,该工具基于TUN接口实现其功能,利用反向TCP/TLS连接建立一条隐蔽的通信信道,支持使用Let’s Encrypt自动生成证书。Ligolo-ng的通信隐蔽性体现在其支持多种连接方式,适应复杂网…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
条件运算符
C中的三目运算符(也称条件运算符,英文:ternary operator)是一种简洁的条件选择语句,语法如下: 条件表达式 ? 表达式1 : 表达式2• 如果“条件表达式”为true,则整个表达式的结果为“表达式1”…...
五年级数学知识边界总结思考-下册
目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解:由来、作用与意义**一、知识点核心内容****二、知识点的由来:从生活实践到数学抽象****三、知识的作用:解决实际问题的工具****四、学习的意义:培养核心素养…...
macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用
文章目录 问题现象问题原因解决办法 问题现象 macOS启动台(Launchpad)多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显,都是Google家的办公全家桶。这些应用并不是通过独立安装的…...
ESP32 I2S音频总线学习笔记(四): INMP441采集音频并实时播放
简介 前面两期文章我们介绍了I2S的读取和写入,一个是通过INMP441麦克风模块采集音频,一个是通过PCM5102A模块播放音频,那如果我们将两者结合起来,将麦克风采集到的音频通过PCM5102A播放,是不是就可以做一个扩音器了呢…...
tree 树组件大数据卡顿问题优化
问题背景 项目中有用到树组件用来做文件目录,但是由于这个树组件的节点越来越多,导致页面在滚动这个树组件的时候浏览器就很容易卡死。这种问题基本上都是因为dom节点太多,导致的浏览器卡顿,这里很明显就需要用到虚拟列表的技术&…...
html css js网页制作成品——HTML+CSS榴莲商城网页设计(4页)附源码
目录 一、👨🎓网站题目 二、✍️网站描述 三、📚网站介绍 四、🌐网站效果 五、🪓 代码实现 🧱HTML 六、🥇 如何让学习不再盲目 七、🎁更多干货 一、👨…...
短视频矩阵系统文案创作功能开发实践,定制化开发
在短视频行业迅猛发展的当下,企业和个人创作者为了扩大影响力、提升传播效果,纷纷采用短视频矩阵运营策略,同时管理多个平台、多个账号的内容发布。然而,频繁的文案创作需求让运营者疲于应对,如何高效产出高质量文案成…...
如何更改默认 Crontab 编辑器 ?
在 Linux 领域中,crontab 是您可能经常遇到的一个术语。这个实用程序在类 unix 操作系统上可用,用于调度在预定义时间和间隔自动执行的任务。这对管理员和高级用户非常有益,允许他们自动执行各种系统任务。 编辑 Crontab 文件通常使用文本编…...
