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 解压玩具双人带…...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
centos 7 部署awstats 网站访问检测
一、基础环境准备(两种安装方式都要做) bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats࿰…...
【机器视觉】单目测距——运动结构恢复
ps:图是随便找的,为了凑个封面 前言 在前面对光流法进行进一步改进,希望将2D光流推广至3D场景流时,发现2D转3D过程中存在尺度歧义问题,需要补全摄像头拍摄图像中缺失的深度信息,否则解空间不收敛…...
Java多线程实现之Callable接口深度解析
Java多线程实现之Callable接口深度解析 一、Callable接口概述1.1 接口定义1.2 与Runnable接口的对比1.3 Future接口与FutureTask类 二、Callable接口的基本使用方法2.1 传统方式实现Callable接口2.2 使用Lambda表达式简化Callable实现2.3 使用FutureTask类执行Callable任务 三、…...
2021-03-15 iview一些问题
1.iview 在使用tree组件时,发现没有set类的方法,只有get,那么要改变tree值,只能遍历treeData,递归修改treeData的checked,发现无法更改,原因在于check模式下,子元素的勾选状态跟父节…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...
PAN/FPN
import torch import torch.nn as nn import torch.nn.functional as F import mathclass LowResQueryHighResKVAttention(nn.Module):"""方案 1: 低分辨率特征 (Query) 查询高分辨率特征 (Key, Value).输出分辨率与低分辨率输入相同。"""def __…...
vulnyx Blogger writeup
信息收集 arp-scan nmap 获取userFlag 上web看看 一个默认的页面,gobuster扫一下目录 可以看到扫出的目录中得到了一个有价值的目录/wordpress,说明目标所使用的cms是wordpress,访问http://192.168.43.213/wordpress/然后查看源码能看到 这…...
CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!
本文介绍了一种名为AnomalyAny的创新框架,该方法利用Stable Diffusion的强大生成能力,仅需单个正常样本和文本描述,即可生成逼真且多样化的异常样本,有效解决了视觉异常检测中异常样本稀缺的难题,为工业质检、医疗影像…...
学习一下用鸿蒙DevEco Studio HarmonyOS5实现百度地图
在鸿蒙(HarmonyOS5)中集成百度地图,可以通过以下步骤和技术方案实现。结合鸿蒙的分布式能力和百度地图的API,可以构建跨设备的定位、导航和地图展示功能。 1. 鸿蒙环境准备 开发工具:下载安装 De…...
