当前位置: 首页 > 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;甚至还可以用来变现…...

深度学习在微纳光子学中的应用

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

黑马Mybatis

Mybatis 表现层&#xff1a;页面展示 业务层&#xff1a;逻辑处理 持久层&#xff1a;持久数据化保存 在这里插入图片描述 Mybatis快速入门 ![在这里插入图片描述](https://i-blog.csdnimg.cn/direct/6501c2109c4442118ceb6014725e48e4.png //logback.xml <?xml ver…...

多场景 OkHttpClient 管理器 - Android 网络通信解决方案

下面是一个完整的 Android 实现&#xff0c;展示如何创建和管理多个 OkHttpClient 实例&#xff0c;分别用于长连接、普通 HTTP 请求和文件下载场景。 <?xml version"1.0" encoding"utf-8"?> <LinearLayout xmlns:android"http://schemas…...

【位运算】消失的两个数字(hard)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

学校招生小程序源码介绍

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

智能在线客服平台:数字化时代企业连接用户的 AI 中枢

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

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

ETLCloud可能遇到的问题有哪些?常见坑位解析

数据集成平台ETLCloud&#xff0c;主要用于支持数据的抽取&#xff08;Extract&#xff09;、转换&#xff08;Transform&#xff09;和加载&#xff08;Load&#xff09;过程。提供了一个简洁直观的界面&#xff0c;以便用户可以在不同的数据源之间轻松地进行数据迁移和转换。…...

相机从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…...