排序——归并排序及排序章节总结
前面的文章中 我们详细介绍了排序的概念,插入排序,交换排序与选择排序,大家可以通过下面的链接再去学习:
排序的概念及插入排序
交换排序
选择排序
这篇文章就详细介绍一下另一种排序算法:归并排序以及对排序章节进行一下总结。
一,归并排序基本概念
归并:将两个或两个以上的有序表组合成一个新有序表
2-路归并排序
排序过程
初始序列看成n个有序子序列,每个子序列长度为1
两两合并,得到 ë n/2 û 个长度为2或1的有序子序列
例:
将两个顺序表合成一个有序表
两个有序子序列的归并
设两个有序表存放在同一数组中相邻的位置上:R[low..mid]和R[mid + 1..high]
每次分别从两个表中取出一个记录进行关键字的比较,将较小者放入T[1ow..high]中
在代码中实现:
void Merge(RedType R[],RedType &T[],int low,int mid,int high)
{ i=low;j=mid+1;k=low; while(i<=mid&&j<=high) //将R中记录由小到大地并入T中{ if(R[i].key<=R[j].key) T[k]=R[i++]; else T[k]=R[j++]; } while(i<=mid) T[k++]=R[i++]; //将剩余的R[low..mid]复制到T中 while(j<=high) T[k++]=R[j++];//将剩余的R[j.high]复制到T中
}
归并排序的递归
2-路归并排序将R[low..high]中的记录归并排序后放入T[low..high]中。当序列长度等于1时,递归结束,否则:
① 将当前序列一分为二,求出分裂点mid = (low+high)/2;
② 对子序列R[low..mid]递归,结果放入S[low..mid]中;
③ 对子序列R[mid + 1..high]递归,结果放入S[mid + 1..high]中;
具体的代码实现递归过程:
void MSort(RedType R[],RedType &T[],int low,int high)
{ if(low==high) T[low]=R[low]; else{ mid=(low+high)/2; //将当前序列一分为二,求出分裂点mid MSort(R,S,low,mid); //R[low..mid]递归,结果放入S[low..mid] MSort(R,S,mid+1,high);//R[mid+1..high]递归,结果放入S[mid+1..high]Merge(S,T,low,mid,high);//将S[low..mid]和S[mid+1..high]归并到T[low..high]}
}
下面是一段完整的归并排序实例:
#include <stdio.h>// 合并两个子数组的函数
void merge(int arr[], int l, int m, int r) {int i, j, k;int n1 = m - l + 1; // 左子数组的大小int n2 = r - m; // 右子数组的大小int L[n1], R[n2]; // 创建临时数组// 复制数据到临时数组 L[] 和 R[]for (i = 0; i < n1; i++)L[i] = arr[l + i];for (j = 0; j < n2; j++)R[j] = arr[m + 1 + j];// 合并临时数组回 arr[l..r]i = 0; // 初始化第一个子数组的索引j = 0; // 初始化第二个子数组的索引k = l; // 初始化合并后的子数组的索引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++;}
}// 归并排序的主函数
void mergeSort(int arr[], int l, int r) {if (l < r) {int m = l + (r - l) / 2; // 计算中间点mergeSort(arr, l, m); // 递归排序左半部分mergeSort(arr, m + 1, r); // 递归排序右半部分merge(arr, l, m, r); // 合并左右两部分}
}int main() {int arr[] = {12, 11, 13, 5, 6, 7};int arr_size = sizeof(arr) / sizeof(arr[0]);printf("给定的数组是 :");for (int i = 0; i < arr_size; i++)printf("%d ", arr[i]);printf("\n");mergeSort(arr, 0, arr_size - 1); // 对整个数组进行归并排序printf("排序后的数组是: ");for (int i = 0; i < arr_size; i++)printf("%d ", arr[i]);return 0;
}
算法分析
时间效率:O(nlog2n)
空间效率:O(n)
稳 定 性:稳定
二,排序章节总结
各种排序算法的性能:
首先通过下面这个图表对比一下
(数据不是顺次后移时将导致方法不稳定)
按平均时间排序方法分为四类
O(n2)、O(nlogn)、O(n1+e )、O(n)
•快速排序是基于比较的内部排序中平均性能最好的
• 基数排序时间复杂度最低,但对关键字结构有要求
知道各级关键字的主次关系
知道各级关键字的取值范围
为避免顺序存储时大量移动记录的时间开销,可考虑用链表作为存储结构:直接插入排序、归并排序、基数排序 。
不宜采用链表作为存储结构的折半插入排序、希尔排序、快速排序、堆排序 。
排序算法的选择规则:
当n较大时
(1)分布随机,稳定性不做要求,则采用快速排序
(2)内存允许,要求排序稳定时,则采用归并排序
(3)可能会出现正序或逆序,稳定性不做要求,则采用堆排序或归并排序
当n较小时
(1)基本有序,则采用直接插入排序
(2)分布随机,则采用简单选择排序,若排序码不接近逆序,也可以采用直接插入排序。
到此排序就结束了, 如果文章对你有用的话请点个赞支持一下吧!
相关文章:

排序——归并排序及排序章节总结
前面的文章中 我们详细介绍了排序的概念,插入排序,交换排序与选择排序,大家可以通过下面的链接再去学习: 排序的概念及插入排序 交换排序 选择排序 这篇文章就详细介绍一下另一种排序算法:归并排序以及…...
python的readline()和readlines()
readlines() readlines() 是 Python 中用于从文件对象中读取所有行的方法。它会一次性读取整个文件内容,并将每一行作为一个字符串存储在一个列表中返回。 使用方法和返回值 使用 readlines() 方法可以读取文件的所有内容,每一行作为列表中的一个元素…...

【ARM】使用JasperGold和Cadence IFV科普
#工作记录# 原本希望使用CCI自带的验证脚本来验证修改过后的address map decoder,但是发现需要使用JasperGold或者Cadence家的IFV的工具,我们公司没有,只能搜搜资料做一下科普了解,希望以后能用到吧。这个虽然跟ARM没啥关系不过在…...

深入探讨极限编程(XP):技术实践与频繁发布的艺术
目录 前言1. 极限编程的核心原则1.1 沟通1.2 简单1.3 反馈1.4 勇气1.5 尊重 2. 关键实践2.1 结对编程2.1.1 提高代码质量2.1.2 促进知识共享2.1.3 增强团队协作 2.2 测试驱动开发(TDD)2.2.1 提升代码可靠性2.2.2 提高代码可维护性2.2.3 鼓励良好设计 2.3…...
【代码随想录_Day30】1049. 最后一块石头的重量 II 494. 目标和 474.一和零
Day30 OK,今日份的打卡!第三十天 以下是今日份的总结最后一块石头的重量 II目标和一和零 以下是今日份的总结 1049 最后一块石头的重量 II 494 目标和 474 一和零 今天的题目难度不低,掌握技巧了就会很简单,尽量还是写一些简洁代…...

【时时三省】tessy 集成测试:小白入门指导手册
目录 1,创建集成测试模块且分析源文件 2,设置测试环境 3,TIE界面设置相关函数 4,SCE界面增加用例 5,编辑数据 6,用例所对应的测试函数序列 7,添加 work task 函数 8,为测试场景添加函数 9,为函数赋值 10,编辑时间序列的数值 11,执行用例 12,其他注意事项…...

通过vagrant与VirtualBox 创建虚拟机
1.下载vagrant与VirtualBox【windows版本案例】 1.1 vagrant 下载地址 【按需下载】 https://developer.hashicorp.com/vagrant/install?product_intentvagranthttps://developer.hashicorp.com/vagrant/install?product_intentvagrant 1.2 VirtualBox 下载地址 【按需下载…...
第13章 更多的结构化命令《Linux命令行与Shell脚本编程大全笔记》
13.1 For命令 格式:for var in list;dofor命令默认按照空格、制表符、换行符作为字段分隔符区分单个值,如果某个值含有空格要使用双引号从命令中读取值列表for state in $(cat $file)更改字段分隔符IFS(internal field separator)IFS$\n可能的需求&…...

【计算机网络】学习指南及导论
个人主页:【😊个人主页】 系列专栏:【❤️计算机网络】 文章目录 前言我们为什么要学计算机网络?计算机网络概述计算机网络的分类按交换技术分类按使用者分类按传输介质分类按覆盖网络分类按覆盖网络分类 局域网的连接方式有线连接…...

安装mitmproxy失败
安装mitmproxy失败记录 问题记录 问题记录 安装mitmproxy时,发现一直报错 这里的报错是因为我缺少了编译的环境 我是win7 的系统,缺少C的环境,所以我安装的时候源码包无法编译。 单独安装了这个包,依旧是失败的。 1.尝试用以下命…...

安装adb和常用命令
下载ADB安装包 https://dl.google.com/android/repository/platform-tools-latest-windows.zip 解压安装包 解压如上下载的安装包,然后复制adb.exe所在的文件地址 配置环境变量 我的电脑——>右键属性——>高级系统设置——>环境变量——>系统变量—…...

C++ 几何计算库
代码 #include <iostream> #include <list> #include <CGAL/Simple_cartesian.h> #include <CGAL/AABB_tree.h> #include <CGAL/AABB_traits.h> #include <CGAL/AABB_segment_primitive.h> #include <CGAL/Polygon_2.h>typedef CGAL…...

云动态摘要 2024-07-16
给您带来云厂商的最新动态,最新产品资讯和最新优惠更新。 最新优惠与活动 数据库上云优选 阿里云 2024-07-04 RDS、PolarDB、Redis、MongoDB 全系产品新用户低至首年6折起! [免费体验]智能助手ChatBI上线 腾讯云 2024-07-02 基于混元大模型打造&…...
数仓工具—Hive基础之临时表及示例
Hive基础之临时表及示例 临时表是应用程序自动管理在大型或复杂查询执行期间生成的中间数据的一种便捷方式。Hive 0.14 及更高版本支持临时表。可以在用户会话中像使用普通表一样多次使用它们。在本文中,我们将介绍 Apache Hive 临时表,以及如何创建和使用限制的示例。 Hiv…...
机体坐标系和导航坐标系
目录 机体坐标系(Body Frame)例子:无人机的机体坐标系 导航坐标系(Navigation Frame)例子:地球固定的导航坐标系 具体例子说明机体坐标系描述导航坐标系描述 总结 机体坐标系(Body Frame&#x…...

软件测试——web单功能测试
工作职责: 1.负责产品系统测试,包括功能测试、性能测试、稳定性测试、用户场景测试、可靠性测试等。 2.负责测试相关文档的编写,包括测试计划、测试用例、测试报告等。 3.负责自动化测试框架、用例的维护。 岗位要求: 1.熟练…...

django-ckeditor富文本编辑器
一.安装django-ckeditor 1.安装 pip install django-ckeditor2.注册应用 INSTALLED_APPS [...ckeditor, ]3.配置model from ckeditor.fields import RichTextFieldcontent RichTextField()4.在项目中manage.py文件下重新执行迁移,生成迁移文件 py…...

鸿蒙模拟器(HarmonyOS Emulator)Beta申请审核流程
文 | Promise Sun 一.背景: 鸿蒙项目开发需要使用模拟器进行开发测试,但目前想在DevEco Studio开发工具中使用模拟器就必须到华为官网进行报名申请,参加“鸿蒙模拟器(HarmonyOS Emulator)Beta活动申请”。 申请审核通…...

VUE:跨域配置代理服务器
//在vite.config。js中,同插件配置同级进行配置server:{proxy:{"/myrequest":{//代理域名,可自行修改target:"https://m.wzj.com/",//访问服务器的目标域名changeOrigin:true,//允许跨域configure:(proxy,options) > {proxy.on(&…...

Redis实战—附近商铺、用户签到、UV统计
本博客为个人学习笔记,学习网站与详细见:黑马程序员Redis入门到实战 P88 - P95 目录 附近商铺 数据导入 功能实现 用户签到 签到功能 连续签到统计 UV统计 附近商铺 利用Redis中的GEO数据结构实现附近商铺功能,常见命令如下图所示。…...
KubeSphere 容器平台高可用:环境搭建与可视化操作指南
Linux_k8s篇 欢迎来到Linux的世界,看笔记好好学多敲多打,每个人都是大神! 题目:KubeSphere 容器平台高可用:环境搭建与可视化操作指南 版本号: 1.0,0 作者: 老王要学习 日期: 2025.06.05 适用环境: Ubuntu22 文档说…...
后进先出(LIFO)详解
LIFO 是 Last In, First Out 的缩写,中文译为后进先出。这是一种数据结构的工作原则,类似于一摞盘子或一叠书本: 最后放进去的元素最先出来 -想象往筒状容器里放盘子: (1)你放进的最后一个盘子(…...
Spring Boot 实现流式响应(兼容 2.7.x)
在实际开发中,我们可能会遇到一些流式数据处理的场景,比如接收来自上游接口的 Server-Sent Events(SSE) 或 流式 JSON 内容,并将其原样中转给前端页面或客户端。这种情况下,传统的 RestTemplate 缓存机制会…...

Mybatis逆向工程,动态创建实体类、条件扩展类、Mapper接口、Mapper.xml映射文件
今天呢,博主的学习进度也是步入了Java Mybatis 框架,目前正在逐步杨帆旗航。 那么接下来就给大家出一期有关 Mybatis 逆向工程的教学,希望能对大家有所帮助,也特别欢迎大家指点不足之处,小生很乐意接受正确的建议&…...
java调用dll出现unsatisfiedLinkError以及JNA和JNI的区别
UnsatisfiedLinkError 在对接硬件设备中,我们会遇到使用 java 调用 dll文件 的情况,此时大概率出现UnsatisfiedLinkError链接错误,原因可能有如下几种 类名错误包名错误方法名参数错误使用 JNI 协议调用,结果 dll 未实现 JNI 协…...

[ICLR 2022]How Much Can CLIP Benefit Vision-and-Language Tasks?
论文网址:pdf 英文是纯手打的!论文原文的summarizing and paraphrasing。可能会出现难以避免的拼写错误和语法错误,若有发现欢迎评论指正!文章偏向于笔记,谨慎食用 目录 1. 心得 2. 论文逐段精读 2.1. Abstract 2…...

高等数学(下)题型笔记(八)空间解析几何与向量代数
目录 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…...
MySQL账号权限管理指南:安全创建账户与精细授权技巧
在MySQL数据库管理中,合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号? 最小权限原则…...

排序算法总结(C++)
目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指:同样大小的样本 **(同样大小的数据)**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...
MySQL 部分重点知识篇
一、数据库对象 1. 主键 定义 :主键是用于唯一标识表中每一行记录的字段或字段组合。它具有唯一性和非空性特点。 作用 :确保数据的完整性,便于数据的查询和管理。 示例 :在学生信息表中,学号可以作为主键ÿ…...