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好用,甚至还可以用来变现…...

深度学习在微纳光子学中的应用
深度学习在微纳光子学中的主要应用方向 深度学习与微纳光子学的结合主要集中在以下几个方向: 逆向设计 通过神经网络快速预测微纳结构的光学响应,替代传统耗时的数值模拟方法。例如设计超表面、光子晶体等结构。 特征提取与优化 从复杂的光学数据中自…...

黑马Mybatis
Mybatis 表现层:页面展示 业务层:逻辑处理 持久层:持久数据化保存 在这里插入图片描述 Mybatis快速入门 
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...

学校招生小程序源码介绍
基于ThinkPHPFastAdminUniApp开发的学校招生小程序源码,专为学校招生场景量身打造,功能实用且操作便捷。 从技术架构来看,ThinkPHP提供稳定可靠的后台服务,FastAdmin加速开发流程,UniApp则保障小程序在多端有良好的兼…...

智能在线客服平台:数字化时代企业连接用户的 AI 中枢
随着互联网技术的飞速发展,消费者期望能够随时随地与企业进行交流。在线客服平台作为连接企业与客户的重要桥梁,不仅优化了客户体验,还提升了企业的服务效率和市场竞争力。本文将探讨在线客服平台的重要性、技术进展、实际应用,并…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式
点一下关注吧!!!非常感谢!!持续更新!!! 🚀 AI篇持续更新中!(长期更新) 目前2025年06月05日更新到: AI炼丹日志-28 - Aud…...

ETLCloud可能遇到的问题有哪些?常见坑位解析
数据集成平台ETLCloud,主要用于支持数据的抽取(Extract)、转换(Transform)和加载(Load)过程。提供了一个简洁直观的界面,以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

相机从app启动流程
一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

Reasoning over Uncertain Text by Generative Large Language Models
https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829https://ojs.aaai.org/index.php/AAAI/article/view/34674/36829 1. 概述 文本中的不确定性在许多语境中传达,从日常对话到特定领域的文档(例如医学文档)(Heritage 2013;Landmark、Gulbrandsen 和 Svenevei…...