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

归并排序——二路归并排序

目录

1、简述

2、复杂度

3、稳定性

4、例子


1、简述

二路归并排序(Merge Sort)是一种基于分治法的排序算法,通过将数组递归地拆分成两部分,分别排序后再合并,从而实现整个数组的有序。二路归并排序具有稳定性和高效性,是一种非常经典的排序算法。

实现步骤

  1. 分割
    • 将数组分成两部分,分别对每部分进行递归排序。
  2. 合并
    • 将两个已排序的部分合并成一个有序的整体。

2、复杂度

  • 时间复杂度

    • 最佳情况:O(n log n)
    • 最坏情况:O(n log n)
    • 平均情况:O(n log n)
  • 空间复杂度

    • O(n),需要额外的存储空间来合并两个子数组。

3、稳定性

归并排序是一种稳定的排序算法,因为在合并时保持了相同元素的相对顺序。

4、例子

#include <iostream>
#include <vector>// 合并两个有序子数组
void merge(std::vector<int>& arr, int left, int mid, int right) {int n1 = mid - left + 1;int n2 = right - mid;// 创建临时数组std::vector<int> L(n1);std::vector<int> R(n2);// 复制数据到临时数组 L[] 和 R[]for (int i = 0; i < n1; ++i)L[i] = arr[left + i];for (int i = 0; i < n2; ++i)R[i] = arr[mid + 1 + i];// 合并临时数组到原数组int i = 0, j = 0, k = left;while (i < n1 && j < n2) {if (L[i] <= R[j]) {arr[k] = L[i];++i;} else {arr[k] = R[j];++j;}++k;}// 复制剩余元素(如果有)while (i < n1) {arr[k] = L[i];++i;++k;}while (j < n2) {arr[k] = R[j];++j;++k;}
}// 递归实现归并排序
void mergeSort(std::vector<int>& arr, int left, int right) {if (left < right) {int mid = left + (right - left) / 2;// 递归排序两个子数组mergeSort(arr, left, mid);mergeSort(arr, mid + 1, right);// 合并两个已排序的子数组merge(arr, left, mid, right);}
}// 测试代码
int main() {std::vector<int> array = {12, 11, 13, 5, 6, 7};mergeSort(array, 0, array.size() - 1);std::cout << "Sorted array is \n";for (int num : array)std::cout << num << " ";std::cout << std::endl;return 0;
}

 快捷跳转: 

  • 排序算法概述

生命不息,学习不止,若有不正确的地方,欢迎指正。

相关文章:

归并排序——二路归并排序

目录 1、简述 2、复杂度 3、稳定性 4、例子 1、简述 二路归并排序&#xff08;Merge Sort&#xff09;是一种基于分治法的排序算法&#xff0c;通过将数组递归地拆分成两部分&#xff0c;分别排序后再合并&#xff0c;从而实现整个数组的有序。二路归并排序具有稳定性和高…...

java-StringBuilder

StringBuilder 是 Java 中一个重要的类&#xff0c;它提供了可变的字符序列&#xff0c;可以用来高效地执行字符串操作&#xff0c;如拼接、替换和删除等。在 Java 编程中&#xff0c;字符串操作是非常常见的&#xff0c;而 StringBuilder 类为我们提供了简单、高效的方式来完成…...

数据结构 | 超详细讲解七大排序(C语言实现,含动图,多方法!)

目录 ​编辑 排序的概念 常见排序算法 ​编辑 1.冒泡排序 &#x1f379;图解 &#x1f973;代码实现 &#x1f914;时间复杂度 2.插入排序 &#x1f379;图解 &#x1f334;深度剖析 &#x1f34e;代码思路 &#x1f973;代码实现 &#x1f914;时间复杂度 3.希尔…...

企业自建邮件系统的优势,安全性更高,功能更灵活,维护更便捷

在当今企业信息管理的浪潮中&#xff0c;企业邮件系统显得尤为关键&#xff0c;它不仅加强了内部的沟通效率&#xff0c;还对外展示了企业的专业形象。然而&#xff0c;传统租用企业邮箱服务存在一些不足&#xff0c;如缺乏灵活性、数据管理混乱和难以实现个性化需求&#xff0…...

Softing工业助力微软解锁工业数据,推动AI技术在工业领域的发展

一 概览 Softing作为全球先进工业通信解决方案供应商之一&#xff0c;与微软合作共同推出了众多工业边缘产品&#xff0c;以实现工业应用中OT和IT的连接。这些产品可在基于微软Azure云平台的IIoT解决方案中轻松集成和运行&#xff0c;并为AI解锁工业数据&#xff0c;还可通过A…...

企微自动化机器人的应用与前景

一、引言 随着信息技术的飞速发展&#xff0c;企业对于提高内部运营效率、降低人力成本的需求日益迫切。在这样的背景下&#xff0c;企微自动化机器人应运而生&#xff0c;以其高效、便捷的特点&#xff0c;迅速成为企业内部的得力助手。本文将深入探讨企微自动化机器人的应用现…...

从零开始:如何用Electron将chatgpt-plus.top 打包成EXE文件

文章目录 从零开始&#xff1a;如何用Electron将chatgpt-plus.top 打包成EXE文件准备工作&#xff1a;Node.js和npm国内镜像加速下载初始化你的Electron项目创建你的Electron应用运行你的Electron应用为你的应用设置图标打包成EXE文件结语 从零开始&#xff1a;如何用Electron将…...

基于RNN和Transformer的词级语言建模 代码分析 log_softmax

基于RNN和Transformer的词级语言建模 代码分析 log_softmax flyfish Word-level Language Modeling using RNN and Transformer word_language_model PyTorch 提供的 word_language_model 示例展示了如何使用循环神经网络RNN(GRU或LSTM)和 Transformer 模型进行词级语言建模…...

Python爬虫要掌握哪些东西

学习Python爬虫,你需要掌握以下几个关键方面的知识: 文章目录 Python基础:首先,确保你对Python语言有良好的理解,包括基本语法、数据结构(如列表、字典、集合等)、函数、类和对象、模块和包的使用等。# 有一个数字列表,要创建新的列表,元素是原列表中每个元素的平方 …...

FPGA-ARM架构与分类

ARM架构&#xff0c;曾称进阶精简指令集机器&#xff08;Advanced RISC Machine&#xff09;更早称作Acorn RISC Machine&#xff0c;是一个32位精简指令集&#xff08;RISC&#xff09;处理器架构。 主要是根据FPGA zynq-7000的芯片编写的知识思维导图总结,废话不多说自取吧 …...

docker网络详解

1. 网络模式 1.1 网络结构 当安装Docker以后&#xff0c;会自动创建三个网络。可以使用docker network ls命令列出这些网络。 $ docker network ls NETWORK ID NAME DRIVER SCOPE 440aefe8afa3 bridge bridge local aa8d6325580f host host …...

设计软件有哪些?效果工具篇(1),渲染100邀请码1a12

设计师会用到很多渲染效果和后期处理的工具&#xff0c;这里我们介绍一些。 1、AfterBurn AfterBurn是为Autodesk 3ds Max开发的专业级别的体积照明和效果插件。它提供了一系列强大的特效功能&#xff0c;包括烟雾、火焰、云彩等。用户可以利用AfterBurn创建逼真的环境效果&a…...

Iphone自动化指令每隔固定天数打开闹钟关闭闹钟(二)

1.首先在搜索和操作里搜索“查找日期日程" 1.1.然后过滤条件开始日期选择”是今天“ 1.2.增加过滤条件&#xff0c;日历是这里选择”工作“ 1.3.增加过滤条件&#xff0c;选择标题&#xff0c;是这里选择”workDay“ 1.4选中限制&#xff0c;日历日程只要一个&#xff0c;…...

计算机网络错题答案汇总

王道学习 第1章 计算机网络体系结构 1.1 1.2...

Fortigate防火墙二层接口的几种实现方式

初始配置 FortiGate出厂配置默认地址为192.168.1.99&#xff08;MGMT接口&#xff09;&#xff0c;可以通过https的方式进行web管理&#xff08;默认用户名admin&#xff0c;密码为空&#xff09;&#xff0c;不同型号设备用于管理的接口略有不同。 console接口的配置 防火墙…...

如何永久擦除Android手机中的所有个人数据?

在这个数字化的时代&#xff0c;确保您的个人数据的安全和隐私至关重要。如果您计划出售或回收您的Android手机&#xff0c;了解如何正确擦除Android手机是至关重要的。本综合指南将引导您通过安全擦除Android手机的分步过程&#xff0c;以保护您的敏感信息。 手机是极其敏感的…...

使用手机小程序给证件照换底色

临时遇到一个需求&#xff0c;需要给证件照换底色。原始图像如下 最终需要换成红底的。 本次使用一款小程序&#xff02;泰世茂证件照&#xff02;&#xff0c;打开该小程序&#xff0c;如下图所示 单击开始制作&#xff0c;然后选择二寸红底&#xff0c;如下图所示 然后单击相…...

C语言杂谈:函数栈帧,函数调用时到底发生了什么

我们都知道在调用函数时&#xff0c;要为函数在栈上开辟空间&#xff0c;函数后续内容都会在栈帧空间中保存&#xff0c;如非静态局部变量&#xff0c;返回值等。这段空间就叫栈帧。 当函数调用&#xff0c;就会开辟栈帧空间&#xff0c;函数返回时&#xff0c;栈帧空间就会被释…...

【Qt】win10,QTableWidget表头下无分隔线的问题

1. 现象 2. 原因 win10系统的UI样式默认是这样的。 3. 解决 - 方法1 //横向表头ui->table->horizontalHeader()->setStyleSheet("QHeaderView::section{""border-top:0px solid #E5E5E5;""border-left:0px solid #E5E5E5;""bord…...

前端 实现有时间限制的缓存

首先我们需要创建一个名为TimeLimitedCache的构造函数&#xff0c;然后定义一些方法&#xff0c;如set, get,和count。以下是具体的示例代码&#xff1a; // 定义 TimeLimitedCache 构造函数 var TimeLimitedCache function( ) {// 初始化一个空的 cache 对象&#xff0c;用于…...

Spark 之 入门讲解详细版(1)

1、简介 1.1 Spark简介 Spark是加州大学伯克利分校AMP实验室&#xff08;Algorithms, Machines, and People Lab&#xff09;开发通用内存并行计算框架。Spark在2013年6月进入Apache成为孵化项目&#xff0c;8个月后成为Apache顶级项目&#xff0c;速度之快足见过人之处&…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

BCS 2025|百度副总裁陈洋:智能体在安全领域的应用实践

6月5日&#xff0c;2025全球数字经济大会数字安全主论坛暨北京网络安全大会在国家会议中心隆重开幕。百度副总裁陈洋受邀出席&#xff0c;并作《智能体在安全领域的应用实践》主题演讲&#xff0c;分享了在智能体在安全领域的突破性实践。他指出&#xff0c;百度通过将安全能力…...

【python异步多线程】异步多线程爬虫代码示例

claude生成的python多线程、异步代码示例&#xff0c;模拟20个网页的爬取&#xff0c;每个网页假设要0.5-2秒完成。 代码 Python多线程爬虫教程 核心概念 多线程&#xff1a;允许程序同时执行多个任务&#xff0c;提高IO密集型任务&#xff08;如网络请求&#xff09;的效率…...

实现弹窗随键盘上移居中

实现弹窗随键盘上移的核心思路 在Android中&#xff0c;可以通过监听键盘的显示和隐藏事件&#xff0c;动态调整弹窗的位置。关键点在于获取键盘高度&#xff0c;并计算剩余屏幕空间以重新定位弹窗。 // 在Activity或Fragment中设置键盘监听 val rootView findViewById<V…...

安全突围:重塑内生安全体系:齐向东在2025年BCS大会的演讲

文章目录 前言第一部分&#xff1a;体系力量是突围之钥第一重困境是体系思想落地不畅。第二重困境是大小体系融合瓶颈。第三重困境是“小体系”运营梗阻。 第二部分&#xff1a;体系矛盾是突围之障一是数据孤岛的障碍。二是投入不足的障碍。三是新旧兼容难的障碍。 第三部分&am…...

JavaScript 数据类型详解

JavaScript 数据类型详解 JavaScript 数据类型分为 原始类型&#xff08;Primitive&#xff09; 和 对象类型&#xff08;Object&#xff09; 两大类&#xff0c;共 8 种&#xff08;ES11&#xff09;&#xff1a; 一、原始类型&#xff08;7种&#xff09; 1. undefined 定…...

书籍“之“字形打印矩阵(8)0609

题目 给定一个矩阵matrix&#xff0c;按照"之"字形的方式打印这个矩阵&#xff0c;例如&#xff1a; 1 2 3 4 5 6 7 8 9 10 11 12 ”之“字形打印的结果为&#xff1a;1&#xff0c;…...

Mysql故障排插与环境优化

前置知识点 最上层是一些客户端和连接服务&#xff0c;包含本 sock 通信和大多数jiyukehuduan/服务端工具实现的TCP/IP通信。主要完成一些简介处理、授权认证、及相关的安全方案等。在该层上引入了线程池的概念&#xff0c;为通过安全认证接入的客户端提供线程。同样在该层上可…...

GraphRAG优化新思路-开源的ROGRAG框架

目前的如微软开源的GraphRAG的工作流程都较为复杂&#xff0c;难以孤立地评估各个组件的贡献&#xff0c;传统的检索方法在处理复杂推理任务时可能不够有效&#xff0c;特别是在需要理解实体间关系或多跳知识的情况下。先说结论&#xff0c;看完后感觉这个框架性能上不会比Grap…...