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

【数据结构与算法】归并排序

归并排序

归并排序(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}

相关文章:

【数据结构与算法】归并排序

归并排序 归并排序&#xff08;MERGE-SORT&#xff09;是利用归并的思想实现的排序方法&#xff0c;该算法采用经典的分治&#xff08;divide-and-conquer&#xff09;策略&#xff08;分治法将问题分&#xff08;divide&#xff09;成一些小的问题然后递归求解&#xff0c;而…...

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&#xff08;用…...

IPv6 over IPv4隧道配置举例

配置IPv6 over IPv4手动隧道示例 组网需求 如图1所示&#xff0c;两台IPv6主机分别通过SwitchA和SwitchC与IPv4骨干网络连接&#xff0c;客户希望两台IPv6主机能通过IPv4骨干网互通。 图1 配置IPv6 over IPv4手动隧道组网图 配置思路 配置IPv6 over IPv4手动隧道的思路如下&…...

【GitOps系列】使用 ArgoCD 快速打造GitOps工作流

文章目录 ArgoCD简介ArgoCD安装访问ArgoCDGitOps 工作流总览创建 ArgoCD 应用检查 ArgoCD 同步状态访问应用 连接 GitOps 工作流体验 GitOps 工作流生产建议1&#xff09;修改默认密码2&#xff09;配置 Ingress 和 TLS3&#xff09;使用 Webhook 触发 ArgoCD4&#xff09;将源…...

C#|无法打开cs文件设计窗口

报错信息&#xff1a;To prevent possible data loss before loading the designer, the following errors must be resolved: 解决方案&#xff1a;实不相瞒我把项目解决方案名称改短了就可以了。。有其他原因或者解决方案望不吝赐教。。...

【SpringBoot笔记36】SpringBoot自定义WebSocketHandler集成WebSocket

这篇文章,主要介绍SpringBoot自定义WebSocketHandler集成WebSocket。 目录 一、SpringBoot集成WebSocket 1.1、添加WebSocket依赖 1.2、自定义WebSocketHandler 1.3、注册WebSocket服务端...

flutter 图片相关

官方链接&#xff1a;https://api.flutter.dev/flutter/widgets/Image-class.html 图片基本使用 显示本地图片时,要在pubspec.yaml文件里面添加如:(注意空格) assets: - assets/images/logo.png Fit属性&#xff1a; BoxFit.cover最常用 显示可能拉伸&#xff0c;可能裁…...

将上位机程序从PC的window系统迁移至Intel NUC的无桌面版ubuntu系统问题记录

将上位机程序从PC的window系统迁移至Intel NUC的无桌面版ubuntu系统 问题一 网口失效 问题描述&#xff1a;NUC关机状态下&#xff0c;将网口与路由器连接&#xff0c;网络指示灯闪烁&#xff1b;NUC开机后&#xff0c;网络指示灯熄灭&#xff0c;使用ping命令&#xff0c;既…...

CHI中的error处理

Error Handling Error types 包含两种sub-packet级别的error, 和两种packe级别的error; Packet level error Data Error, DERR □ 访问的地址是正确的&#xff0c;但是访问的数据有错误&#xff1b;通常是在数据崩溃的时候使用&#xff0c;例如ECC&#xf…...

如何使用 PHP 进行数据库缓存处理?

当你想要让你的PHP应用程序更快时&#xff0c;数据库缓存是一个重要的工具。它可以帮助你避免频繁地查询数据库&#xff0c;提高应用程序的响应速度。不过&#xff0c;在进行数据库缓存处理时&#xff0c;需要注意一些细节&#xff0c;否则可能会得到相反的结果。下面&#xff…...

新版巨量广告投放技巧分析

新版广告系统&#xff0c;计划出价40&#xff0c;转化成本特别低只有21&#xff0c;同时消耗也比较慢 为什么刚开始成本都比较低&#xff0c;跑着跑着成本就高了&#xff0c;像这种情况一般如何操作&#xff1f; 一: 为什么会出现成本和出价差这么多 1&#xff1a; 系统对账…...

Vue3 导出excel

&#x1f642;博主&#xff1a;锅盖哒 &#x1f642;文章核心&#xff1a;导出excel 目录 首先&#xff0c;你需要安装xlsx库。可以使用npm或yarn来安装&#xff1a; 在Vue组件中&#xff0c;你可以使用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设计模式【模板方法模式】

内容&#xff1a;定义一个操作中的算法的骨架&#xff0c;而将一些步骤延迟到子类中。模板方法使得子类可以不改变一个算法的结构即可重定义该算法某特定步骤。 角色&#xff1a; 抽象类&#xff08;AbstractClass&#xff09;&#xff1a;定义抽象的原子操作&#xff08;钩子…...

谷粒商城第六天-实现功能的前序工作(网关的配置 跨域配置)

目录 一、为什么要做这项工作 1.1 为什么要配置网关 1.2 为什么要使用网关统一配置跨域 二、网关配置 三、统一跨域配置 四、总结 一、为什么要做这项工作 1.1 为什么要配置网关 我们知道网关的作用其实主要就是进行路由的&#xff0c;也就是根据前端发送到网关的请求&…...

为什么说国内数字孪生平台gis架构采用Cesium是不错的选择?

Gis作为数字孪生平台开发中重要的一环对数字孪生平台是否好用是一个重要的判定方式&#xff0c;国内数字孪生软件在融合GIS系统方面采取了多种方式&#xff0c;例如Unity或Unreal Engine等游戏引擎&#xff0c;以增强数字孪生的空间感知和空间分析能力&#xff0c;提供更全面、…...

前端面试的性能优化部分(1)每篇10题

1. 懒加载的概念 懒加载&#xff08;Lazy Loading&#xff09;是一种优化技术&#xff0c;它用于延迟加载页面资源&#xff0c;只在需要时才加载特定的内容&#xff0c;而不是在页面初始加载时一次性加载所有资源。懒加载的目的是提高页面加载速度和性能&#xff0c;尤其对于单…...

GitLab备份升级

数据备份(默认的备份目录在/var/opt/gitlab/backups/下&#xff0c;生成一个以时间节点命名的tar包。) gitlab-rake gitlab:backup:create新建repo源&#xff0c;升级新版本的gitlab vim /etc/yum.repos.d/gitlab-ce.repo [gitlab-ce] namegitlab-ce baseurlhttps://mirrors.…...

Matlab实现遗传算法仿真(附上40个仿真源码)

遗传算法&#xff08;Genetic Algorithm&#xff0c;GA&#xff09;是一种基于生物进化理论的优化算法&#xff0c;通过模拟自然界中的遗传过程&#xff0c;来寻找最优解。 在遗传算法中&#xff0c;每个解被称为个体&#xff0c;每个个体由一组基因表示&#xff0c;每个基因是…...

git使用(由浅到深)

目录流程图 1. 分布式版本控制与集中式版本控制 1.1 集中式版本控制 集中式版本控制系统有:CVS和SVN它们的主要特点是单一的集中管理的服务器&#xff0c;保存所有文件的修订版本&#xff1b;协同开发人员通过客户端连接到这台服务器&#xff0c;取出最新的文件或者提交更新…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

SciencePlots——绘制论文中的图片

文章目录 安装一、风格二、1 资源 安装 # 安装最新版 pip install githttps://github.com/garrettj403/SciencePlots.git# 安装稳定版 pip install SciencePlots一、风格 简单好用的深度学习论文绘图专用工具包–Science Plot 二、 1 资源 论文绘图神器来了&#xff1a;一行…...

k8s从入门到放弃之Ingress七层负载

k8s从入门到放弃之Ingress七层负载 在Kubernetes&#xff08;简称K8s&#xff09;中&#xff0c;Ingress是一个API对象&#xff0c;它允许你定义如何从集群外部访问集群内部的服务。Ingress可以提供负载均衡、SSL终结和基于名称的虚拟主机等功能。通过Ingress&#xff0c;你可…...

基于服务器使用 apt 安装、配置 Nginx

&#x1f9fe; 一、查看可安装的 Nginx 版本 首先&#xff0c;你可以运行以下命令查看可用版本&#xff1a; apt-cache madison nginx-core输出示例&#xff1a; nginx-core | 1.18.0-6ubuntu14.6 | http://archive.ubuntu.com/ubuntu focal-updates/main amd64 Packages ng…...

鸿蒙中用HarmonyOS SDK应用服务 HarmonyOS5开发一个医院挂号小程序

一、开发准备 ​​环境搭建​​&#xff1a; 安装DevEco Studio 3.0或更高版本配置HarmonyOS SDK申请开发者账号 ​​项目创建​​&#xff1a; File > New > Create Project > Application (选择"Empty Ability") 二、核心功能实现 1. 医院科室展示 /…...

P3 QT项目----记事本(3.8)

3.8 记事本项目总结 项目源码 1.main.cpp #include "widget.h" #include <QApplication> int main(int argc, char *argv[]) {QApplication a(argc, argv);Widget w;w.show();return a.exec(); } 2.widget.cpp #include "widget.h" #include &q…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

【VLNs篇】07:NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...