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

0基础学C#笔记10:归并排序法

文章目录

  • 前言
  • 一、递归的方式
  • 二、代码
  • 总结


前言

将一个大的无序数组有序,我们可以把大的数组分成两个,然后对这两个数组分别进行排序,之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的,所以在合并的时候是很快的。


一、递归的方式

通过递归的方式将大的数组一直分割,直到数组的大小为 1,此时只有一个元素,那么该数组就是有序的了,之后再把两个数组大小为1的合并成一个大小为2的,再把两个大小为2的合并成4的 …… 直到全部小的数组合并起来。

为方便理解我还准备了动图:
在这里插入图片描述

二、代码

public class MergeSort {// 归并排序public static int[] mergeSort(int[] arr, int left, int right) {// 如果 left == right,表示数组只有一个元素,则不用递归排序if (left < right) {// 把大的数组分隔成两个数组int mid = (left + right) / 2;// 对左半部分进行排序arr = mergeSort(arr, left, mid);// 对右半部分进行排序arr = mergeSort(arr, mid + 1, right);//进行合并merge(arr, left, mid, right);}return arr;}// 合并函数,把两个有序的数组合并起来// arr[left..mif]表示一个数组,arr[mid+1 .. right]表示一个数组private static void merge(int[] arr, int left, int mid, int right) {//先用一个临时数组把他们合并汇总起来int[] a = new int[right - left + 1];int i = left;int j = mid + 1;int k = 0;while (i <= mid && j <= right) {if (arr[i] < arr[j]) {a[k++] = arr[i++];} else {a[k++] = arr[j++];}}while(i <= mid) a[k++] = arr[i++];while(j <= right) a[k++] = arr[j++];// 把临时数组复制到原数组for (i = 0; i < k; i++) {arr[left++] = a[i];}}
}

然而面试官要你写个非递归式的归并排序怎么办?别怕,我这还撸了个非递归式的归并排序,代码如下:

public class MergeSort {// 非递归式的归并排序public static int[] mergeSort(int[] arr) {int n = arr.length;// 子数组的大小分别为1,2,4,8...// 刚开始合并的数组大小是1,接着是2,接着4....for (int i = 1; i < n; i += i) {//进行数组进行划分int left = 0;int mid = left + i - 1;int right = mid + i;//进行合并,对数组大小为 i 的数组进行两两合并while (right < n) {// 合并函数和递归式的合并函数一样merge(arr, left, mid, right);left = right + 1;mid = left + i - 1;right = mid + i;}// 还有一些被遗漏的数组没合并,千万别忘了// 因为不可能每个字数组的大小都刚好为 iif (left < n && mid < n) {merge(arr, left, mid, n - 1);}}return arr;}
}

总结

性质:
1、时间复杂度:O(nlogn)
2、空间复杂度:O(n)
3、稳定排序
4、非原地排序

相关文章:

0基础学C#笔记10:归并排序法

文章目录 前言一、递归的方式二、代码总结 前言 将一个大的无序数组有序&#xff0c;我们可以把大的数组分成两个&#xff0c;然后对这两个数组分别进行排序&#xff0c;之后在把这两个数组合并成一个有序的数组。由于两个小的数组都是有序的&#xff0c;所以在合并的时候是很…...

nlohmann json:通过for遍历object和array

object和array可以使用数for进行遍历: #include <iostream> #include <nlohmann/json.hpp> using namespace std; using json = nlohmann::json;auto checkJsonType(json& x) {if(x.type() == json::value_t::null){cout<<x<<" is null&quo…...

适配器模式:将不兼容的接口转换为可兼容的接口

适配器模式&#xff1a;将不兼容的接口转换为可兼容的接口 什么是适配器模式&#xff1f; 适配器模式是一种结构型设计模式&#xff0c;用于将一个类的接口转换为客户端所期望的另一个接口。它允许不兼容的类能够合作&#xff0c;使得原本由于接口不匹配而无法工作的类能够一…...

【量化课程】07_量化回测

文章目录 7.1 pandas计算策略评估指标数据准备净值曲线年化收益率波动率最大回撤Alpha系数和Beta系数夏普比率信息比率 7.2 聚宽平台量化回测实践平台介绍策略实现 7.3 Backtrader平台量化回测实践Backtrader简介Backtrader量化回测框架实践 7.4 BigQuant量化框架实战BigQuant简…...

竞赛项目 深度学习花卉识别 - python 机器视觉 opencv

文章目录 0 前言1 项目背景2 花卉识别的基本原理3 算法实现3.1 预处理3.2 特征提取和选择3.3 分类器设计和决策3.4 卷积神经网络基本原理 4 算法实现4.1 花卉图像数据4.2 模块组成 5 项目执行结果6 最后 0 前言 &#x1f525; 优质竞赛项目系列&#xff0c;今天要分享的是 &a…...

用对角线去遍历矩阵

声明 该系列文章仅仅展示个人的解题思路和分析过程&#xff0c;并非一定是优质题解&#xff0c;重要的是通过分析和解决问题能让我们逐渐熟练和成长&#xff0c;从新手到大佬离不开一个磨练的过程&#xff0c;加油&#xff01; 原题链接 用对角线遍历矩阵https://leetcode.c…...

【vue】点击按钮弹出卡片,点击卡片中的取消按钮取消弹出的卡片(附代码)

实现思路&#xff1a; 在按钮上绑定一个点击事件&#xff0c;默认是true&#xff1b;在export default { }中注册变量给卡片标签用v-if判断是否要显示卡片&#xff0c;ture则显示&#xff1b;在卡片里面写好你想要展示的数据&#xff1b;给卡片添加一个取消按钮&#xff0c;绑…...

【K8S】pod 基础概念讲解

目录 Pod基础概念&#xff1a;在Kubrenetes集群中Pod有如下两种使用方式&#xff1a;pause容器使得Pod中的所有容器可以共享两种资源&#xff1a;网络和存储。总结&#xff1a;kubernetes中的pause容器主要为每个容器提供以下功能&#xff1a;Kubernetes设计这样的Pod概念和特殊…...

ASP.NET Core中间件记录管道图和内置中间件

管道记录 下图显示了 ASP.NET Core MVC 和 Razor Pages 应用程序的完整请求处理管道 中间件组件在文件中添加的顺序Program.cs定义了请求时调用中间件组件的顺序以及响应的相反顺序。该顺序对于安全性、性能和功能至关重要。 内置中间件记录 内置中间件原文翻译MiddlewareDe…...

[系统安全] 五十二.DataCon竞赛 (1)2020年Coremail钓鱼邮件识别及分类详解

您可能之前看到过我写的类似文章,为什么还要重复撰写呢?只是想更好地帮助初学者了解病毒逆向分析和系统安全,更加成体系且不破坏之前的系列。因此,我重新开设了这个专栏,准备系统整理和深入学习系统安全、逆向分析和恶意代码检测,“系统安全”系列文章会更加聚焦,更加系…...

Android学习之路(3) 布局

线性布局LinearLayout 前几个小节的例程中&#xff0c;XML文件用到了LinearLayout布局&#xff0c;它的学名为线性布局。顾名思义&#xff0c;线性布局 像是用一根线把它的内部视图串起来&#xff0c;故而内部视图之间的排列顺序是固定的&#xff0c;要么从左到右排列&#xf…...

Python实现GA遗传算法优化XGBoost回归模型(XGBRegressor算法)项目实战

说明&#xff1a;这是一个机器学习实战项目&#xff08;附带数据代码文档视频讲解&#xff09;&#xff0c;如需数据代码文档视频讲解可以直接到文章最后获取。 1.项目背景 遗传算法&#xff08;Genetic Algorithm&#xff0c;GA&#xff09;最早是由美国的 John holland于20世…...

C#软件外包开发流程

C# 是一种由微软开发的多范式编程语言&#xff0c;常用于开发各种类型的应用程序&#xff0c;从桌面应用程序到移动应用程序和Web应用程序。下面和大家分享 C# 编程学习流程&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#…...

队列的实现

1.队列的概念 队列&#xff1a;只允许在一端进行插入数据操作&#xff0c;在另一端进行删除数据操作的特殊线性表&#xff0c;队列具有先进先出FIFO(First In First Out)。 入队列&#xff1a;进行插入操作的一端称为队尾 出队列&#xff1a;进行删除操作的一端称为队头 2.队列…...

Node + Express 后台开发 —— 起步

Node Express 后台开发 —— 起步 前面陆续学习了一下 node、npm、模块&#xff0c;也稍尝试 Express&#xff0c;感觉得换一个思路加快进行。 比如笔者对前端的开发已较熟悉&#xff0c;如果领导给一个内部小网站的需求&#xff0c;难道说你得给我配置一个后端&#xff1f;…...

Python学习笔记第五十七天(Pandas 数据清洗)

Python学习笔记第五十七天 Pandas 数据清洗Pandas 清洗空值isnull() Pandas替换单元格mean()median()mode() Pandas 清洗格式错误数据Pandas 清洗错误数据Pandas 清洗重复数据duplicated()drop_duplicates() 后记 Pandas 数据清洗 数据清洗是对一些没有用的数据进行处理的过程…...

Elasticsearch的一些基本概念

文章目录 基本概念&#xff1a;文档和索引JSON文档元数据索引REST API 节点和集群节点Master eligible节点和Master节点Data Node 和 Coordinating Node其它节点 分片(Primary Shard & Replica Shard)分片的设定操作命令 基本概念&#xff1a;文档和索引 Elasticsearch是面…...

Guitar Pro8专业版吉他学习、绘谱、创作软件

Guitar Pro 8 专业版更强大&#xff01;更优雅&#xff01;更完美&#xff01;Guitar Pro 8.0 五年磨一剑&#xff01;多达30项功能优化&#xff01;Guitar Pro8 版本一共更新近30项功能&#xff0c;令吉他打谱更出色&#xff01;Guitar Pro8 是自2017年4月发布7.0之后发布的最…...

SpringBoot复习(39)Servlet容器的自动配置原理

Servlet容器自动配置类为ServletWebServerFactoryAutoConfiguration 可以看到通过Import注解导入了三个配置类&#xff1a; 通过这个这三个配置类可以看出&#xff0c;它们都使用了ConditionalOnClass注解&#xff0c;当类路径存在tomcat相关的类时&#xff0c;会配置一个T…...

【前端 | CSS】盒模型clientWidth、clientHeight、offsetWidht、offsetHeight

图 先看一个例子 html <div class"container"><div class"item">内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容内容</div> </…...

Qt/C++开发监控GB28181系统/取流协议/同时支持udp/tcp被动/tcp主动

一、前言说明 在2011版本的gb28181协议中&#xff0c;拉取视频流只要求udp方式&#xff0c;从2016开始要求新增支持tcp被动和tcp主动两种方式&#xff0c;udp理论上会丢包的&#xff0c;所以实际使用过程可能会出现画面花屏的情况&#xff0c;而tcp肯定不丢包&#xff0c;起码…...

Python爬虫(二):爬虫完整流程

爬虫完整流程详解&#xff08;7大核心步骤实战技巧&#xff09; 一、爬虫完整工作流程 以下是爬虫开发的完整流程&#xff0c;我将结合具体技术点和实战经验展开说明&#xff1a; 1. 目标分析与前期准备 网站技术分析&#xff1a; 使用浏览器开发者工具&#xff08;F12&…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

Java 加密常用的各种算法及其选择

在数字化时代&#xff0c;数据安全至关重要&#xff0c;Java 作为广泛应用的编程语言&#xff0c;提供了丰富的加密算法来保障数据的保密性、完整性和真实性。了解这些常用加密算法及其适用场景&#xff0c;有助于开发者在不同的业务需求中做出正确的选择。​ 一、对称加密算法…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

ip子接口配置及删除

配置永久生效的子接口&#xff0c;2个IP 都可以登录你这一台服务器。重启不失效。 永久的 [应用] vi /etc/sysconfig/network-scripts/ifcfg-eth0修改文件内内容 TYPE"Ethernet" BOOTPROTO"none" NAME"eth0" DEVICE"eth0" ONBOOT&q…...

Java编程之桥接模式

定义 桥接模式&#xff08;Bridge Pattern&#xff09;属于结构型设计模式&#xff0c;它的核心意图是将抽象部分与实现部分分离&#xff0c;使它们可以独立地变化。这种模式通过组合关系来替代继承关系&#xff0c;从而降低了抽象和实现这两个可变维度之间的耦合度。 用例子…...

三分算法与DeepSeek辅助证明是单峰函数

前置 单峰函数有唯一的最大值&#xff0c;最大值左侧的数值严格单调递增&#xff0c;最大值右侧的数值严格单调递减。 单谷函数有唯一的最小值&#xff0c;最小值左侧的数值严格单调递减&#xff0c;最小值右侧的数值严格单调递增。 三分的本质 三分和二分一样都是通过不断缩…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...