【数据结构与算法】归并排序
归并排序
归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而治(conquer)的阶段则将分的阶段得到的各答案“修补”在一起,即分而治之)。

说明:
可以看到这种结构很像一颗完全二叉树,本文的归并排序我们采用递归去实现(也可以采用迭代的方式去实现)。分阶段可以理解为就是递归拆分子序列的过程。
代码实现:
public class MergerSort {public static void main(String[] args) {int[] arr = {8, 4, 5, 7, 1, 3, 6, 2};int[] temp = new int[arr.length];mergeSort(arr, 0, arr.length - 1, temp);System.out.println(Arrays.toString(arr));}public static void mergeSort(int[] arr, int left, int right, int[] temp) {if (left < right) {int mid = (left + right) / 2; // 中间索引// 向左递归进行分解mergeSort(arr, left, mid, temp);// 向右递归进行分解mergeSort(arr, mid + 1, right, temp);// 到合并merge(arr, left, mid, right, temp);}}/*** 归并排序(合并)** @param arr 排序的初始数组* @param left 左边有序序列的初始索引* @param mid 中间索引* @param right 右边索引* @param temp 中转数组*/public static void merge(int[] arr, int left, int mid, int right, int[] temp) {int i = left; // 初始化 i,左边有序序列的初始索引int j = mid + 1; // 初始化 j,右边有序序列的初始索引int t = 0; // 指向 temp 数组的当前索引// 一、// 先把左右两边(有序)的数据按照规则填充到 temp 数组// 直到左右两边的有序序列,有一边处理完毕为止while (i <= mid && j <= right) {// 若果左边的有序序列的当前元素,小于等于右边有序序列的当前元素// 即将左边的当前元素,填充到 temp 数组if (arr[i] <= arr[j]) {temp[t] = arr[i];t += 1;i += 1;} else { // 反之,将右边的当前元素,填充到 temp 数组temp[t] = arr[j];t += 1;j += 1;}}// 二、// 把剩余数据的一边的数据依次全部填充到 temp 数组while (i <= mid) { // 左边有序序列还有剩余元素temp[t] = arr[i];t += 1;i += 1;}while (j <= right) { // 右边有序序列还有剩余元素temp[t] = arr[j];t += 1;j += 1;}// 三、// 将 temp 数组的元素拷贝到 arr// 注意:并不是每次都拷贝所有t = 0;int tempLift = left;while (tempLift <= right) {arr[tempLift] = temp[t];t += 1;tempLift += 1;}}
}
性能测试:
public static void main(String[] args) {int[] arr = new int[8000000];for (int i = 0; i < 8000000; i++) {arr[i] = (int) (Math.random() * 8000000); // 生成一个 [0,8000000) 随机数}int[] temp = new int[arr.length];long start = System.currentTimeMillis();mergeSort(arr, 0, arr.length - 1, temp);long end = System.currentTimeMillis();System.out.println("通过归并排序的时间:" + (end - start)); // 1504ms}
相关文章:
【数据结构与算法】归并排序
归并排序 归并排序(MERGE-SORT)是利用归并的思想实现的排序方法,该算法采用经典的分治(divide-and-conquer)策略(分治法将问题分(divide)成一些小的问题然后递归求解,而…...
OSG3.6.5 + VS2017前期准备及编译
OSG3.6.5 VS2017前期准备及编译 1、前期准备 1.1、osg稳定版本源码 Stable releases (openscenegraph.com) 1.2、osg依赖项 Dependencies (openscenegraph.com) 1.3、osg测试及演示数据 Data Resources (openscenegraph.com) 1.4、安装doxygen和Graphviz(用…...
IPv6 over IPv4隧道配置举例
配置IPv6 over IPv4手动隧道示例 组网需求 如图1所示,两台IPv6主机分别通过SwitchA和SwitchC与IPv4骨干网络连接,客户希望两台IPv6主机能通过IPv4骨干网互通。 图1 配置IPv6 over IPv4手动隧道组网图 配置思路 配置IPv6 over IPv4手动隧道的思路如下&…...
【GitOps系列】使用 ArgoCD 快速打造GitOps工作流
文章目录 ArgoCD简介ArgoCD安装访问ArgoCDGitOps 工作流总览创建 ArgoCD 应用检查 ArgoCD 同步状态访问应用 连接 GitOps 工作流体验 GitOps 工作流生产建议1)修改默认密码2)配置 Ingress 和 TLS3)使用 Webhook 触发 ArgoCD4)将源…...
C#|无法打开cs文件设计窗口
报错信息:To prevent possible data loss before loading the designer, the following errors must be resolved: 解决方案:实不相瞒我把项目解决方案名称改短了就可以了。。有其他原因或者解决方案望不吝赐教。。...
【SpringBoot笔记36】SpringBoot自定义WebSocketHandler集成WebSocket
这篇文章,主要介绍SpringBoot自定义WebSocketHandler集成WebSocket。 目录 一、SpringBoot集成WebSocket 1.1、添加WebSocket依赖 1.2、自定义WebSocketHandler 1.3、注册WebSocket服务端...
flutter 图片相关
官方链接:https://api.flutter.dev/flutter/widgets/Image-class.html 图片基本使用 显示本地图片时,要在pubspec.yaml文件里面添加如:(注意空格) assets: - assets/images/logo.png Fit属性: BoxFit.cover最常用 显示可能拉伸,可能裁…...
将上位机程序从PC的window系统迁移至Intel NUC的无桌面版ubuntu系统问题记录
将上位机程序从PC的window系统迁移至Intel NUC的无桌面版ubuntu系统 问题一 网口失效 问题描述:NUC关机状态下,将网口与路由器连接,网络指示灯闪烁;NUC开机后,网络指示灯熄灭,使用ping命令,既…...
CHI中的error处理
Error Handling Error types 包含两种sub-packet级别的error, 和两种packe级别的error; Packet level error Data Error, DERR □ 访问的地址是正确的,但是访问的数据有错误;通常是在数据崩溃的时候使用,例如ECC…...
如何使用 PHP 进行数据库缓存处理?
当你想要让你的PHP应用程序更快时,数据库缓存是一个重要的工具。它可以帮助你避免频繁地查询数据库,提高应用程序的响应速度。不过,在进行数据库缓存处理时,需要注意一些细节,否则可能会得到相反的结果。下面ÿ…...
新版巨量广告投放技巧分析
新版广告系统,计划出价40,转化成本特别低只有21,同时消耗也比较慢 为什么刚开始成本都比较低,跑着跑着成本就高了,像这种情况一般如何操作? 一: 为什么会出现成本和出价差这么多 1: 系统对账…...
Vue3 导出excel
🙂博主:锅盖哒 🙂文章核心:导出excel 目录 首先,你需要安装xlsx库。可以使用npm或yarn来安装: 在Vue组件中,你可以使用xlsx库来生成Excel文件并提供一个导出按钮供用户下载。 在Vue 3中&…...
vue 使用vue-json-viewer 展示 JSON 格式的数据
npm install vue-json-viewer --save<el-button type"primary" click"previewClick">预览</el-button><el-dialog title"预览" :visible.sync"previewVisible" width"70%"><viewer ref"viewer&qu…...
14.python设计模式【模板方法模式】
内容:定义一个操作中的算法的骨架,而将一些步骤延迟到子类中。模板方法使得子类可以不改变一个算法的结构即可重定义该算法某特定步骤。 角色: 抽象类(AbstractClass):定义抽象的原子操作(钩子…...
谷粒商城第六天-实现功能的前序工作(网关的配置 跨域配置)
目录 一、为什么要做这项工作 1.1 为什么要配置网关 1.2 为什么要使用网关统一配置跨域 二、网关配置 三、统一跨域配置 四、总结 一、为什么要做这项工作 1.1 为什么要配置网关 我们知道网关的作用其实主要就是进行路由的,也就是根据前端发送到网关的请求&…...
为什么说国内数字孪生平台gis架构采用Cesium是不错的选择?
Gis作为数字孪生平台开发中重要的一环对数字孪生平台是否好用是一个重要的判定方式,国内数字孪生软件在融合GIS系统方面采取了多种方式,例如Unity或Unreal Engine等游戏引擎,以增强数字孪生的空间感知和空间分析能力,提供更全面、…...
前端面试的性能优化部分(1)每篇10题
1. 懒加载的概念 懒加载(Lazy Loading)是一种优化技术,它用于延迟加载页面资源,只在需要时才加载特定的内容,而不是在页面初始加载时一次性加载所有资源。懒加载的目的是提高页面加载速度和性能,尤其对于单…...
GitLab备份升级
数据备份(默认的备份目录在/var/opt/gitlab/backups/下,生成一个以时间节点命名的tar包。) gitlab-rake gitlab:backup:create新建repo源,升级新版本的gitlab vim /etc/yum.repos.d/gitlab-ce.repo [gitlab-ce] namegitlab-ce baseurlhttps://mirrors.…...
Matlab实现遗传算法仿真(附上40个仿真源码)
遗传算法(Genetic Algorithm,GA)是一种基于生物进化理论的优化算法,通过模拟自然界中的遗传过程,来寻找最优解。 在遗传算法中,每个解被称为个体,每个个体由一组基因表示,每个基因是…...
git使用(由浅到深)
目录流程图 1. 分布式版本控制与集中式版本控制 1.1 集中式版本控制 集中式版本控制系统有:CVS和SVN它们的主要特点是单一的集中管理的服务器,保存所有文件的修订版本;协同开发人员通过客户端连接到这台服务器,取出最新的文件或者提交更新…...
龙虎榜——20250610
上证指数放量收阴线,个股多数下跌,盘中受消息影响大幅波动。 深证指数放量收阴线形成顶分型,指数短线有调整的需求,大概需要一两天。 2025年6月10日龙虎榜行业方向分析 1. 金融科技 代表标的:御银股份、雄帝科技 驱动…...
vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
可靠性+灵活性:电力载波技术在楼宇自控中的核心价值
可靠性灵活性:电力载波技术在楼宇自控中的核心价值 在智能楼宇的自动化控制中,电力载波技术(PLC)凭借其独特的优势,正成为构建高效、稳定、灵活系统的核心解决方案。它利用现有电力线路传输数据,无需额外布…...
WPF八大法则:告别模态窗口卡顿
⚙️ 核心问题:阻塞式模态窗口的缺陷 原始代码中ShowDialog()会阻塞UI线程,导致后续逻辑无法执行: var result modalWindow.ShowDialog(); // 线程阻塞 ProcessResult(result); // 必须等待窗口关闭根本问题:…...
深入浅出Diffusion模型:从原理到实践的全方位教程
I. 引言:生成式AI的黎明 – Diffusion模型是什么? 近年来,生成式人工智能(Generative AI)领域取得了爆炸性的进展,模型能够根据简单的文本提示创作出逼真的图像、连贯的文本,乃至更多令人惊叹的…...
认识CMake并使用CMake构建自己的第一个项目
1.CMake的作用和优势 跨平台支持:CMake支持多种操作系统和编译器,使用同一份构建配置可以在不同的环境中使用 简化配置:通过CMakeLists.txt文件,用户可以定义项目结构、依赖项、编译选项等,无需手动编写复杂的构建脚本…...
Spring Boot + MyBatis 集成支付宝支付流程
Spring Boot MyBatis 集成支付宝支付流程 核心流程 商户系统生成订单调用支付宝创建预支付订单用户跳转支付宝完成支付支付宝异步通知支付结果商户处理支付结果更新订单状态支付宝同步跳转回商户页面 代码实现示例(电脑网站支付) 1. 添加依赖 <!…...
java高级——高阶函数、如何定义一个函数式接口类似stream流的filter
java高级——高阶函数、stream流 前情提要文章介绍一、函数伊始1.1 合格的函数1.2 有形的函数2. 函数对象2.1 函数对象——行为参数化2.2 函数对象——延迟执行 二、 函数编程语法1. 函数对象表现形式1.1 Lambda表达式1.2 方法引用(Math::max) 2 函数接口…...
leetcode_69.x的平方根
题目如下 : 看到题 ,我们最原始的想法就是暴力解决: for(long long i 0;i<INT_MAX;i){if(i*ix){return i;}else if((i*i>x)&&((i-1)*(i-1)<x)){return i-1;}}我们直接开始遍历,我们是整数的平方根,所以我们分两…...
学习 Hooks【Plan - June - Week 2】
一、React API React 提供了丰富的核心 API,用于创建组件、管理状态、处理副作用、优化性能等。本文档总结 React 常用的 API 方法和组件。 1. React 核心 API React.createElement(type, props, …children) 用于创建 React 元素,JSX 会被编译成该函数…...
