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

C# 归并排序

栏目总目录


概念

归并排序是一种分而治之的排序算法。它将一个大数组分成两个小数组,递归地对这两个小数组进行排序,然后将排序好的小数组合并成一个有序的大数组。这个过程一直递归进行,直到数组被拆分成只有一个元素的数组(自然是有序的),然后开始合并过程,直至合并成完全有序的数组。

原理

归并排序的主要原理是分治法(Divide and Conquer):

  1. 分解:将数组分解成两个较小的子数组,直到子数组的大小为1。
  2. 递归求解:递归地对子数组进行排序。
  3. 合并:将已排序的子数组合并成一个大的有序数组。

合并过程中,通常使用两个指针分别指向两个子数组的起始位置,比较两个指针所指向的元素,将较小的元素放入临时数组中,并移动该指针。当某个子数组的所有元素都被复制后,将另一个子数组中剩余的元素直接复制到临时数组的末尾。最后,将临时数组的内容复制回原数组,完成合并。

好处与不足

好处

  • 稳定性:归并排序是一种稳定的排序算法。
  • 时间复杂度:归并排序的时间复杂度为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# 归并排序

栏目总目录 概念 归并排序是一种分而治之的排序算法。它将一个大数组分成两个小数组&#xff0c;递归地对这两个小数组进行排序&#xff0c;然后将排序好的小数组合并成一个有序的大数组。这个过程一直递归进行&#xff0c;直到数组被拆分成只有一个元素的数组&#xff08;自然…...

【请求代理】springboot单机服务基于过滤器Filter实现第三方服务器接口请求代理功能

springboot单机服务基于过滤器Filter实现第三方服务器接口请求代理功能 一、前言二、解决思路三、基于gateway实现四、基于过滤器Filter实现五、问题总结 **注&#xff1a;本文源码获取或者更多资料&#xff0c;关注公众号&#xff1a;技术闲人**一、前言 在项目开发时会遇到w…...

.NET Core异步编程与多线程解析:提升性能与响应能力的关键技术

在.NET Core中&#xff0c;异步编程和多线程是构建高性能应用程序的核心技能。理解这两个概念不仅可以提升应用程序的响应能力&#xff0c;还能优化资源使用。本文将深入剖析异步编程和多线程的关键知识点&#xff0c;提供代码示例&#xff0c;并附上步骤以帮助理解。 1. 异步…...

Photoshop(PS) 抠图简单教程

目录 快速选择 魔棒 钢笔 橡皮擦 蒙版 通道 小结 可以发现&#xff0c;ps逐渐成为必备基础的办公软件。本文让ps新手轻松学会抠图。 快速选择 在抠图之前&#xff0c;先了解下选区的概念。ps中大多数的抠图操作都是基于选区的&#xff0c;先选区再Ctrl J提取选区。而快…...

项目管理中的常用工件(二):可视化工件

项目管理中的常用工件&#xff08;二&#xff09;&#xff1a;可视化工件 亲和图&#xff08;affinity diagram&#xff09;因果图&#xff08;cause-and-effect diagram&#xff09;直方图&#xff08;histogram&#xff09;流程图&#xff08;flowchart&#xff09;散点图&am…...

Git入门与实战:版本控制的艺术

&#x1f341; 作者&#xff1a;知识浅谈&#xff0c;CSDN签约讲师&#xff0c;CSDN博客专家&#xff0c;华为云云享专家&#xff0c;阿里云专家博主 &#x1f4cc; 擅长领域&#xff1a;全栈工程师、爬虫、ACM算法 &#x1f525; 微信&#xff1a;zsqtcyw 联系我领取学习资料 …...

[Mysql-DML数据操作语句]

目录 数据增加&#xff1a;INSERT 全字段插入&#xff1a; 部分字段插入&#xff1a; 一次性添加多条&#xff1a; 数据修改&#xff1a;UPDATE 数据删除&#xff1a;DELECT delete truncate drop 区别 数据增加&#xff1a;INSERT 总体格式&#xff1a;insert into 表…...

Tableau入门|数据可视化与仪表盘搭建

原视频链接&#xff08;up:戴戴戴师兄&#xff09;&#xff0c;文章为笔者的自学笔记&#xff0c;用于复习回顾&#xff0c;原视频下方有原up整理的笔记&#xff0c;更加直观便捷。因为视频中间涉及的细节较多&#xff0c;建议一边操作&#xff0c;一边学习。 整体介绍 可视化…...

API 技术开发分享:连接电商平台数据获取的桥梁

在当今数字化的时代&#xff0c;API&#xff08;Application Programming Interface&#xff0c;应用程序编程接口&#xff09;技术成为了实现不同系统之间通信和数据交换的关键。它就像是一座无形的桥梁&#xff0c;使得各种应用能够相互协作&#xff0c;共享资源&#xff0c;…...

区块链如何助力数字版权保护和内容创作者的权益?

区块链技术可以助力数字版权保护和内容创作者的权益&#xff0c;主要有以下几个方面&#xff1a; 去中心化的版权登记和溯源&#xff1a;区块链可作为一个可信的去中心化数据库&#xff0c;记录并验证数字内容的版权信息。内容创作者可以将自己的作品信息存储在区块链上&#x…...

记一次老旧项目的整体技术升级

最近给公司采购的老旧的 node8 vue2.6 webpack3 npm 项目做构建优化 背景&#xff1a;整个项目 build 一次 20 min &#xff0c;本地冷启动和热更新也忒慢&#xff0c;依赖 npm i 一下也得装个 20 min 众所周知&#xff0c;Node 版本&#xff0c;依赖包管理工具 和 构建工…...

2024年最受欢迎的五大上网审计设备和软件

在2024年的市场上&#xff0c;上网行为审计设备和软件种类繁多&#xff0c;它们帮助企业监控和管理员工的网络活动&#xff0c;确保网络安全并提高工作效率。下面是一些受欢迎的上网行为审计设备和软件。 2024年最受欢迎的上网行为审计设备和软件如下 1.安企神软件&#xff1a…...

sed利用脚本处理文件

一、sed是什么 sed 命令是利用脚本来处理文本文件。它可以依照脚本的指令来处理、编辑文本文件。主要用来自动编 辑一个或多个文件、简化对文件的反复操作、编写转换程序等。 二、sed的原理 读入新的一行内容到缓存空间&#xff1b; 从指定的操作指令中取出第一条指令&…...

泰山派RK3566开发板800x1280MIPI屏设备树补丁

泰山派RK3566开发板800x1280MIPI屏设备树补丁 泰山派下800 X 1280分辨率MIPI屏调试&#xff0c;设备树补丁如下&#xff1a; https://download.csdn.net/download/qq_45143522/89584066 用kernel.patch文件&#xff0c;在泰山派内核源码下打补丁即可完成更新&#xff0c;或者…...

informer中的indexer机制的实现分析与源码解读

1. 背景 client-go工具下的tools/cache.indexer为informer提供缓存与索引的能力。可以实现快速通过索引找到对应的对象(pod, deployment,secret,configmap等)。 indexer再informer机制中的使用图示&#xff1a; indexer包括2部分: 一部分是store用于实际数据的存储&#xff0c;…...

英特尔宣布针对对Llama 3.1进行优化 以提升所有产品的性能

日前Meta正式发布了Llama 3.1开源大模型&#xff0c;以其庞大的参数量和卓越性能&#xff0c;首次在多项基准测试中击败了GPT-4o等业界领先的闭源模型。允许开发者自由地进行微调、蒸馏&#xff0c;甚至在任何地方部署&#xff0c;这种开放性为AI技术的普及和创新提供了无限可能…...

Python3网络爬虫开发实战(1)爬虫基础

一、URL 基础 URL也就是网络资源地址&#xff0c;其满足如下格式规范 scheme://[username:password]hostname[:port][/path][;parameters][?query][#fragment] scheme&#xff1a;协议&#xff0c;常用的协议有 Http&#xff0c;https&#xff0c;ftp等等&#xff1b;usern…...

Redis的五种数据类型与命令

目录 引言 一 Redis的特性 二 Redis的安装 三 Redis的优点 四 Redis的五种数据类型与命令 五 Redis的配置文件 引言 Redis是什么&#xff1f; Remote Dictionary Service(远程字典服务器) Redis 是一个开源的(BSD许可)的&#xff0c;C语言编写的&#xff0c;高性能的数…...

RocketMQ的详细讲解(四种mq的对比(activeMq、rabbitmq、rocketmq、kafka))

20240729 RocketMQ1 mq的三大作用 异步、削峰限流、解耦合2. 四种mq的对比&#xff08;activeMq、rabbitmq、rocketmq、kafka&#xff09;3 rocketmq特点1. 平台无关2. 能提供什么样的功能 4 rocketMq4.1 broker中的标题&#xff0c;来约束读和写4.2 rocketmq的结构4.3 读和写的…...

除了GPT,还有哪些好用的AI工具?

最强AI视频生成&#xff1a;小说文案智能分镜智能识别角色和场景批量Ai绘图自动配音添加音乐一键合成视频百万播放量https://aitools.jurilu.com/ 多得很&#xff0c;这20个免费的国产AI工具&#xff0c;打工人必备&#xff0c;除了比chatGPT好用&#xff0c;甚至还可以用来变现…...

Python爬虫实战:研究MechanicalSoup库相关技术

一、MechanicalSoup 库概述 1.1 库简介 MechanicalSoup 是一个 Python 库,专为自动化交互网站而设计。它结合了 requests 的 HTTP 请求能力和 BeautifulSoup 的 HTML 解析能力,提供了直观的 API,让我们可以像人类用户一样浏览网页、填写表单和提交请求。 1.2 主要功能特点…...

第19节 Node.js Express 框架

Express 是一个为Node.js设计的web开发框架&#xff0c;它基于nodejs平台。 Express 简介 Express是一个简洁而灵活的node.js Web应用框架, 提供了一系列强大特性帮助你创建各种Web应用&#xff0c;和丰富的HTTP工具。 使用Express可以快速地搭建一个完整功能的网站。 Expre…...

谷歌浏览器插件

项目中有时候会用到插件 sync-cookie-extension1.0.0&#xff1a;开发环境同步测试 cookie 至 localhost&#xff0c;便于本地请求服务携带 cookie 参考地址&#xff1a;https://juejin.cn/post/7139354571712757767 里面有源码下载下来&#xff0c;加在到扩展即可使用FeHelp…...

Redis相关知识总结(缓存雪崩,缓存穿透,缓存击穿,Redis实现分布式锁,如何保持数据库和缓存一致)

文章目录 1.什么是Redis&#xff1f;2.为什么要使用redis作为mysql的缓存&#xff1f;3.什么是缓存雪崩、缓存穿透、缓存击穿&#xff1f;3.1缓存雪崩3.1.1 大量缓存同时过期3.1.2 Redis宕机 3.2 缓存击穿3.3 缓存穿透3.4 总结 4. 数据库和缓存如何保持一致性5. Redis实现分布式…...

376. Wiggle Subsequence

376. Wiggle Subsequence 代码 class Solution { public:int wiggleMaxLength(vector<int>& nums) {int n nums.size();int res 1;int prediff 0;int curdiff 0;for(int i 0;i < n-1;i){curdiff nums[i1] - nums[i];if( (prediff > 0 && curdif…...

【Web 进阶篇】优雅的接口设计:统一响应、全局异常处理与参数校验

系列回顾&#xff1a; 在上一篇中&#xff0c;我们成功地为应用集成了数据库&#xff0c;并使用 Spring Data JPA 实现了基本的 CRUD API。我们的应用现在能“记忆”数据了&#xff01;但是&#xff0c;如果你仔细审视那些 API&#xff0c;会发现它们还很“粗糙”&#xff1a;有…...

自然语言处理——Transformer

自然语言处理——Transformer 自注意力机制多头注意力机制Transformer 虽然循环神经网络可以对具有序列特性的数据非常有效&#xff0c;它能挖掘数据中的时序信息以及语义信息&#xff0c;但是它有一个很大的缺陷——很难并行化。 我们可以考虑用CNN来替代RNN&#xff0c;但是…...

Netty从入门到进阶(二)

二、Netty入门 1. 概述 1.1 Netty是什么 Netty is an asynchronous event-driven network application framework for rapid development of maintainable high performance protocol servers & clients. Netty是一个异步的、基于事件驱动的网络应用框架&#xff0c;用于…...

Caliper 负载(Workload)详细解析

Caliper 负载(Workload)详细解析 负载(Workload)是 Caliper 性能测试的核心部分,它定义了测试期间要执行的具体合约调用行为和交易模式。下面我将全面深入地讲解负载的各个方面。 一、负载模块基本结构 一个典型的负载模块(如 workload.js)包含以下基本结构: use strict;/…...

手机平板能效生态设计指令EU 2023/1670标准解读

手机平板能效生态设计指令EU 2023/1670标准解读 以下是针对欧盟《手机和平板电脑生态设计法规》(EU) 2023/1670 的核心解读&#xff0c;综合法规核心要求、最新修正及企业合规要点&#xff1a; 一、法规背景与目标 生效与强制时间 发布于2023年8月31日&#xff08;OJ公报&…...