C# 归并排序
栏目总目录
概念
归并排序是一种分而治之的排序算法。它将一个大数组分成两个小数组,递归地对这两个小数组进行排序,然后将排序好的小数组合并成一个有序的大数组。这个过程一直递归进行,直到数组被拆分成只有一个元素的数组(自然是有序的),然后开始合并过程,直至合并成完全有序的数组。
原理
归并排序的主要原理是分治法(Divide and Conquer):
- 分解:将数组分解成两个较小的子数组,直到子数组的大小为1。
- 递归求解:递归地对子数组进行排序。
- 合并:将已排序的子数组合并成一个大的有序数组。
合并过程中,通常使用两个指针分别指向两个子数组的起始位置,比较两个指针所指向的元素,将较小的元素放入临时数组中,并移动该指针。当某个子数组的所有元素都被复制后,将另一个子数组中剩余的元素直接复制到临时数组的末尾。最后,将临时数组的内容复制回原数组,完成合并。
好处与不足
好处:
- 稳定性:归并排序是一种稳定的排序算法。
- 时间复杂度:归并排序的时间复杂度为O(n log n),在平均、最好和最差情况下都是一致的。
- 分而治之:易于并行实现,适合在并行计算环境中使用。
不足:
- 空间复杂度:归并排序需要额外的空间来存储临时数组,空间复杂度为O(n)。
- 自顶向下:归并排序是自顶向下的递归算法,对于非常大的数据集,可能会因为递归深度过大而导致栈溢出。
应用场景
- 适用于大数据量的排序,尤其是在并行计算环境中。
- 需要稳定性排序的场合,如归并排序可以很好地保持相等元素的原始顺序。
- 外部排序中,归并排序是常用的算法之一,因为它可以有效地处理存储在外部存储设备(如硬盘)上的大量数据。
示例代码
class MergeSort
{// 合并两个已排序的数组段private static void Merge(int[] arr, int left, int mid, int right){int n1 = mid - left + 1;int n2 = right - mid;// 创建临时数组int[] L = new int[n1];int[] R = new int[n2];// 拷贝数据到临时数组for (int i = 0; i < n1; i++)L[i] = arr[left + i];for (int j = 0; j < n2; j++)R[j] = arr[mid + 1 + j];// 合并临时数组回到原数组arr[l..r]int i = 0, j = 0;int k = left;while (i < n1 && j < n2){if (L[i] <= R[j]){arr[k] = L[i];i++;}else{arr[k] = R[j];j++;}k++;}// 拷贝L[]的剩余元素while (i < n1){arr[k] = L[i];i++;k++;}// 拷贝R[]的剩余元素while (j < n2){arr[k] = R[j];j++;k++;}}// 主函数来排序arr[l..r]public static void Sort(int[] arr, int left, int right){if (left < right){// 同(l+r)/2,但是防止了大数的溢出int mid = left + (right - left) / 2;// 分别对左右子数组进行排序Sort(arr, left, mid);Sort(arr, mid + 1, right);// 合并结果Merge(arr, left, mid, right);}}
相关文章:
C# 归并排序
栏目总目录 概念 归并排序是一种分而治之的排序算法。它将一个大数组分成两个小数组,递归地对这两个小数组进行排序,然后将排序好的小数组合并成一个有序的大数组。这个过程一直递归进行,直到数组被拆分成只有一个元素的数组(自然…...
【请求代理】springboot单机服务基于过滤器Filter实现第三方服务器接口请求代理功能
springboot单机服务基于过滤器Filter实现第三方服务器接口请求代理功能 一、前言二、解决思路三、基于gateway实现四、基于过滤器Filter实现五、问题总结 **注:本文源码获取或者更多资料,关注公众号:技术闲人**一、前言 在项目开发时会遇到w…...
.NET Core异步编程与多线程解析:提升性能与响应能力的关键技术
在.NET Core中,异步编程和多线程是构建高性能应用程序的核心技能。理解这两个概念不仅可以提升应用程序的响应能力,还能优化资源使用。本文将深入剖析异步编程和多线程的关键知识点,提供代码示例,并附上步骤以帮助理解。 1. 异步…...
Photoshop(PS) 抠图简单教程
目录 快速选择 魔棒 钢笔 橡皮擦 蒙版 通道 小结 可以发现,ps逐渐成为必备基础的办公软件。本文让ps新手轻松学会抠图。 快速选择 在抠图之前,先了解下选区的概念。ps中大多数的抠图操作都是基于选区的,先选区再Ctrl J提取选区。而快…...
项目管理中的常用工件(二):可视化工件
项目管理中的常用工件(二):可视化工件 亲和图(affinity diagram)因果图(cause-and-effect diagram)直方图(histogram)流程图(flowchart)散点图&am…...
Git入门与实战:版本控制的艺术
🍁 作者:知识浅谈,CSDN签约讲师,CSDN博客专家,华为云云享专家,阿里云专家博主 📌 擅长领域:全栈工程师、爬虫、ACM算法 🔥 微信:zsqtcyw 联系我领取学习资料 …...
[Mysql-DML数据操作语句]
目录 数据增加:INSERT 全字段插入: 部分字段插入: 一次性添加多条: 数据修改:UPDATE 数据删除:DELECT delete truncate drop 区别 数据增加:INSERT 总体格式:insert into 表…...
Tableau入门|数据可视化与仪表盘搭建
原视频链接(up:戴戴戴师兄),文章为笔者的自学笔记,用于复习回顾,原视频下方有原up整理的笔记,更加直观便捷。因为视频中间涉及的细节较多,建议一边操作,一边学习。 整体介绍 可视化…...
API 技术开发分享:连接电商平台数据获取的桥梁
在当今数字化的时代,API(Application Programming Interface,应用程序编程接口)技术成为了实现不同系统之间通信和数据交换的关键。它就像是一座无形的桥梁,使得各种应用能够相互协作,共享资源,…...
区块链如何助力数字版权保护和内容创作者的权益?
区块链技术可以助力数字版权保护和内容创作者的权益,主要有以下几个方面: 去中心化的版权登记和溯源:区块链可作为一个可信的去中心化数据库,记录并验证数字内容的版权信息。内容创作者可以将自己的作品信息存储在区块链上&#x…...
记一次老旧项目的整体技术升级
最近给公司采购的老旧的 node8 vue2.6 webpack3 npm 项目做构建优化 背景:整个项目 build 一次 20 min ,本地冷启动和热更新也忒慢,依赖 npm i 一下也得装个 20 min 众所周知,Node 版本,依赖包管理工具 和 构建工…...
2024年最受欢迎的五大上网审计设备和软件
在2024年的市场上,上网行为审计设备和软件种类繁多,它们帮助企业监控和管理员工的网络活动,确保网络安全并提高工作效率。下面是一些受欢迎的上网行为审计设备和软件。 2024年最受欢迎的上网行为审计设备和软件如下 1.安企神软件:…...
sed利用脚本处理文件
一、sed是什么 sed 命令是利用脚本来处理文本文件。它可以依照脚本的指令来处理、编辑文本文件。主要用来自动编 辑一个或多个文件、简化对文件的反复操作、编写转换程序等。 二、sed的原理 读入新的一行内容到缓存空间; 从指定的操作指令中取出第一条指令&…...
泰山派RK3566开发板800x1280MIPI屏设备树补丁
泰山派RK3566开发板800x1280MIPI屏设备树补丁 泰山派下800 X 1280分辨率MIPI屏调试,设备树补丁如下: https://download.csdn.net/download/qq_45143522/89584066 用kernel.patch文件,在泰山派内核源码下打补丁即可完成更新,或者…...
informer中的indexer机制的实现分析与源码解读
1. 背景 client-go工具下的tools/cache.indexer为informer提供缓存与索引的能力。可以实现快速通过索引找到对应的对象(pod, deployment,secret,configmap等)。 indexer再informer机制中的使用图示: indexer包括2部分: 一部分是store用于实际数据的存储,…...
英特尔宣布针对对Llama 3.1进行优化 以提升所有产品的性能
日前Meta正式发布了Llama 3.1开源大模型,以其庞大的参数量和卓越性能,首次在多项基准测试中击败了GPT-4o等业界领先的闭源模型。允许开发者自由地进行微调、蒸馏,甚至在任何地方部署,这种开放性为AI技术的普及和创新提供了无限可能…...
Python3网络爬虫开发实战(1)爬虫基础
一、URL 基础 URL也就是网络资源地址,其满足如下格式规范 scheme://[username:password]hostname[:port][/path][;parameters][?query][#fragment] scheme:协议,常用的协议有 Http,https,ftp等等;usern…...
Redis的五种数据类型与命令
目录 引言 一 Redis的特性 二 Redis的安装 三 Redis的优点 四 Redis的五种数据类型与命令 五 Redis的配置文件 引言 Redis是什么? Remote Dictionary Service(远程字典服务器) Redis 是一个开源的(BSD许可)的,C语言编写的,高性能的数…...
RocketMQ的详细讲解(四种mq的对比(activeMq、rabbitmq、rocketmq、kafka))
20240729 RocketMQ1 mq的三大作用 异步、削峰限流、解耦合2. 四种mq的对比(activeMq、rabbitmq、rocketmq、kafka)3 rocketmq特点1. 平台无关2. 能提供什么样的功能 4 rocketMq4.1 broker中的标题,来约束读和写4.2 rocketmq的结构4.3 读和写的…...
除了GPT,还有哪些好用的AI工具?
最强AI视频生成:小说文案智能分镜智能识别角色和场景批量Ai绘图自动配音添加音乐一键合成视频百万播放量https://aitools.jurilu.com/ 多得很,这20个免费的国产AI工具,打工人必备,除了比chatGPT好用,甚至还可以用来变现…...
变量 varablie 声明- Rust 变量 let mut 声明与 C/C++ 变量声明对比分析
一、变量声明设计:let 与 mut 的哲学解析 Rust 采用 let 声明变量并通过 mut 显式标记可变性,这种设计体现了语言的核心哲学。以下是深度解析: 1.1 设计理念剖析 安全优先原则:默认不可变强制开发者明确声明意图 let x 5; …...
Appium+python自动化(十六)- ADB命令
简介 Android 调试桥(adb)是多种用途的工具,该工具可以帮助你你管理设备或模拟器 的状态。 adb ( Android Debug Bridge)是一个通用命令行工具,其允许您与模拟器实例或连接的 Android 设备进行通信。它可为各种设备操作提供便利,如安装和调试…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
解决本地部署 SmolVLM2 大语言模型运行 flash-attn 报错
出现的问题 安装 flash-attn 会一直卡在 build 那一步或者运行报错 解决办法 是因为你安装的 flash-attn 版本没有对应上,所以报错,到 https://github.com/Dao-AILab/flash-attention/releases 下载对应版本,cu、torch、cp 的版本一定要对…...
【RockeMQ】第2节|RocketMQ快速实战以及核⼼概念详解(二)
升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点,但无自动故障转移能力,Master宕机后需人工切换,期间消息可能无法读取。Slave仅存储数据,无法主动升级为Master响应请求ÿ…...
工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配
AI3D视觉的工业赋能者 迁移科技成立于2017年,作为行业领先的3D工业相机及视觉系统供应商,累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成,通过稳定、易用、高回报的AI3D视觉系统,为汽车、新能源、金属制造等行…...
ArcGIS Pro制作水平横向图例+多级标注
今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作:ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等(ArcGIS出图图例8大技巧),那这次我们看看ArcGIS Pro如何更加快捷的操作。…...
RNN避坑指南:从数学推导到LSTM/GRU工业级部署实战流程
本文较长,建议点赞收藏,以免遗失。更多AI大模型应用开发学习视频及资料,尽在聚客AI学院。 本文全面剖析RNN核心原理,深入讲解梯度消失/爆炸问题,并通过LSTM/GRU结构实现解决方案,提供时间序列预测和文本生成…...
【数据分析】R版IntelliGenes用于生物标志物发现的可解释机器学习
禁止商业或二改转载,仅供自学使用,侵权必究,如需截取部分内容请后台联系作者! 文章目录 介绍流程步骤1. 输入数据2. 特征选择3. 模型训练4. I-Genes 评分计算5. 输出结果 IntelliGenesR 安装包1. 特征选择2. 模型训练和评估3. I-Genes 评分计…...
九天毕昇深度学习平台 | 如何安装库?
pip install 库名 -i https://pypi.tuna.tsinghua.edu.cn/simple --user 举个例子: 报错 ModuleNotFoundError: No module named torch 那么我需要安装 torch pip install torch -i https://pypi.tuna.tsinghua.edu.cn/simple --user pip install 库名&#x…...
