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好用,甚至还可以用来变现…...
【网络】每天掌握一个Linux命令 - iftop
在Linux系统中,iftop是网络管理的得力助手,能实时监控网络流量、连接情况等,帮助排查网络异常。接下来从多方面详细介绍它。 目录 【网络】每天掌握一个Linux命令 - iftop工具概述安装方式核心功能基础用法进阶操作实战案例面试题场景生产场景…...
以下是对华为 HarmonyOS NETX 5属性动画(ArkTS)文档的结构化整理,通过层级标题、表格和代码块提升可读性:
一、属性动画概述NETX 作用:实现组件通用属性的渐变过渡效果,提升用户体验。支持属性:width、height、backgroundColor、opacity、scale、rotate、translate等。注意事项: 布局类属性(如宽高)变化时&#…...
在 Nginx Stream 层“改写”MQTT ngx_stream_mqtt_filter_module
1、为什么要修改 CONNECT 报文? 多租户隔离:自动为接入设备追加租户前缀,后端按 ClientID 拆分队列。零代码鉴权:将入站用户名替换为 OAuth Access-Token,后端 Broker 统一校验。灰度发布:根据 IP/地理位写…...
微服务商城-商品微服务
数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...
ABAP设计模式之---“简单设计原则(Simple Design)”
“Simple Design”(简单设计)是软件开发中的一个重要理念,倡导以最简单的方式实现软件功能,以确保代码清晰易懂、易维护,并在项目需求变化时能够快速适应。 其核心目标是避免复杂和过度设计,遵循“让事情保…...
JVM 内存结构 详解
内存结构 运行时数据区: Java虚拟机在运行Java程序过程中管理的内存区域。 程序计数器: 线程私有,程序控制流的指示器,分支、循环、跳转、异常处理、线程恢复等基础功能都依赖这个计数器完成。 每个线程都有一个程序计数…...
【C++特殊工具与技术】优化内存分配(一):C++中的内存分配
目录 一、C 内存的基本概念 1.1 内存的物理与逻辑结构 1.2 C 程序的内存区域划分 二、栈内存分配 2.1 栈内存的特点 2.2 栈内存分配示例 三、堆内存分配 3.1 new和delete操作符 4.2 内存泄漏与悬空指针问题 4.3 new和delete的重载 四、智能指针…...
Proxmox Mail Gateway安装指南:从零开始配置高效邮件过滤系统
💝💝💝欢迎莅临我的博客,很高兴能够在这里和您见面!希望您在这里可以感受到一份轻松愉快的氛围,不仅可以获得有趣的内容和知识,也可以畅所欲言、分享您的想法和见解。 推荐:「storms…...
恶补电源:1.电桥
一、元器件的选择 搜索并选择电桥,再multisim中选择FWB,就有各种型号的电桥: 电桥是用来干嘛的呢? 它是一个由四个二极管搭成的“桥梁”形状的电路,用来把交流电(AC)变成直流电(DC)。…...
node.js的初步学习
那什么是node.js呢? 和JavaScript又是什么关系呢? node.js 提供了 JavaScript的运行环境。当JavaScript作为后端开发语言来说, 需要在node.js的环境上进行当JavaScript作为前端开发语言来说,需要在浏览器的环境上进行 Node.js 可…...
