排序——归并排序及排序章节总结

前面的文章中 我们详细介绍了排序的概念,插入排序,交换排序与选择排序,大家可以通过下面的链接再去学习:

​​​​​​排序的概念及插入排序

交换排序

选择排序

这篇文章就详细介绍一下另一种排序算法:归并排序以及对排序章节进行一下总结。

一,归并排序基本概念

归并:将两个或两个以上的有序表组合成一个新有序表

2-路归并排序

排序过程

初始序列看成n有序子序列,每个子序列长度为1

两两合并,得到 ë n/2 û 个长度为21的有序子序列

再两两合并,重复直至得到 一个 长度为 n 的有序序列为止

例:

将两个顺序表合成一个有序表

两个有序子序列的归并

设两个有序表存放在同一数组中相邻的位置上:R[low..mid]R[mid + 1..high]

每次分别从两个表中取出一个记录进行关键字的比较,将较小者放入T[1ow..high]

重复 此过程,直至其中一个表为空,最后将另一非空表中余下的部分直接复制到 T

在代码中实现:

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]中;

④ 调用算法 Merge ,将 S[ low..mid ] S[mid + 1..high] 归并 T[ low..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)分布随机,则采用简单选择排序,若排序码不接近逆序,也可以采用直接插入排序。

 


到此排序就结束了, 如果文章对你有用的话请点个赞支持一下吧!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/378499.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

NineData全面支持PostgreSQL可视化表结构设计

“PostgreSQL 是最像 Oracle 的开源关系型数据库“&#xff0c;也正因为如此&#xff0c;很多企业都青睐 PostgreSQL&#xff0c;拿它当成 Oracle 的替代品。所以毫无疑问&#xff0c;目前 PostgreSQL 在企业中非常常见。 对于直接接触 PostgreSQL 的开发人员而言&#xff0c;…

洛谷 P1056 [NOIP2008 普及组 T2]:排座椅 ← 贪心算法

【题目来源】https://www.luogu.com.cn/problem/P1056https://www.acwing.com/problem/content/436/【题目描述】 上课的时候总有一些同学和前后左右的人交头接耳&#xff0c;这是令小学班主任十分头疼的一件事情。 不过&#xff0c;班主任小雪发现了一些有趣的现象&#xff0c…

算法2--贪心算法

1.老鼠和猫的交易 小老鼠准备了M磅的猫粮&#xff0c;准备去和看守仓库的猫做交易&#xff0c;因为仓库里有小老鼠喜欢吃的五香豆。 仓库有N个房间&#xff1b; 第i个房间有 J[i] 磅的五香豆&#xff0c;并且需要用 F[i] 磅的猫粮去交换&#xff1b; 老鼠不必交换该房间所有的五…

大数据技术基础

一、大数据平台 1.大数据平台方案步骤&#xff1a; ①市场上有哪些大数据平台 ②硬件、系统、业务增长等方面 ③方案是否通过 通过后&#xff1a;按照一期目标投入 先虚拟环境部署联系&#xff0c;再实际部署 《大数据架构介绍》《Hadoop架构解析》《Hadoop集群规划》 《H…

微信小程序毕业设计-汽车维修项目管理系统项目开发实战(附源码+论文)

大家好&#xff01;我是程序猿老A&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;微信小程序毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设计…

ollama + fastgpt 搭建免费本地知识库

目录 1、ollama ollama的一些操作命令: 使用的方式: 2、fastgpt 快速部署: 修改配置: config.json: docker-compose.yml: 运行fastgpt: 访问OneApi: 添加令牌和渠道: 登陆fastgpt,创建知识库和应用 3、总结: 附录: 1. 11434是ollama的端口: 2. m3e 测…

Java 中的正则表达式

转义字符由反斜杠\x组成&#xff0c;用于实现特殊功能当想取消这些特殊功能时可以在前面加上反斜杠\ 例如在Java中当\出现时是转义字符的一部分&#xff0c;具有特殊意义&#xff0c;前面加一个反斜可以取消其特殊意义&#xff0c;表示1个普通的反斜杠\&#xff0c;\\\\表示2个…

【排序算法】1.冒泡排序-C语言实现

冒泡排序&#xff08;Bubble Sort&#xff09;是最简单和最通用的排序方法&#xff0c;其基本思想是&#xff1a;在待排序的一组数中&#xff0c;将相邻的两个数进行比较&#xff0c;若前面的数比后面的数大就交换两数&#xff0c;否则不交换&#xff1b;如此下去&#xff0c;直…

Java红娘婚恋相亲交友系统小程序源码

红娘婚恋相亲交友小程序&#xff1a;遇见爱情&#xff0c;从指尖开始&#x1f496; &#x1f4f1; 掌中红娘&#xff0c;随时待命 &#x1f48c; 在这个数字化时代&#xff0c;爱情也迎来了它的新舞台——“红娘婚恋相亲交友小程序”。只需轻轻一点&#xff0c;你的专属红娘就…

git自动pull同步远程若干分支与本地若干分支

git自动pull同步远程若干分支与本地若干分支 假设远程代码仓库有100个分支&#xff0c;而本地只有10个本地分支与远程分支一一对应&#xff0c;现在要保持本地的这个10个分支与远程一致&#xff0c;最笨的方法是checkout到每个分支&#xff0c;然后一个一个的 git pull origin…

【文心智能体】前几天百度热搜有一条非常有趣的话题《00后疯感工牌》,看看如何通过低代码工作流方式实现图片显示

00后疯感工牌体验&#xff1a;https://mbd.baidu.com/ma/s/6yA90qtM 目录 前言比赛推荐工作流创建工作流入口创建工作流界面工作流界面HTTP工具卡点地方 总结推荐文章 前言 前几天百度热搜有一条非常有有趣《00后疯感工牌》。 想着通过文心智能体去一键生成00后疯感工牌是不是…

打包一个自己的Vivado IP核

写在前面 模块复用是逻辑设计人员必须掌握的一个基本功&#xff0c;通过将成熟模块打包成IP核&#xff0c;可实现重复利用&#xff0c;避免重复造轮子&#xff0c;大幅提高我们的开发效率。 接下来将之前设计的串口接收模块和串口发送模块打包成IP核&#xff0c;再分别调用…

华为USG6000V防火墙安全策略用户认证

目录 一、实验拓扑图 二、要求 三、IP地址规划 四、实验配置 1&#x1f923;防火墙FW1web服务配置 2.网络配置 要求1&#xff1a;DMZ区内的服务器&#xff0c;办公区仅能在办公时间内(9:00-18:00)可以访问&#xff0c;生产区的设备全天可以访问 要求2&#xff1a;生产区不…

list模拟实现【C++】

文章目录 全部的实现代码放在了文章末尾准备工作包含头文件定义命名空间类的成员变量为什么节点类是用struct而不是class呢&#xff1f;为什么要写get_head_node? 迭代器迭代器在list类里的实例化和重命名普通迭代器operator->()的作用是什么&#xff1f; const迭代器反向迭…

tkinter-TinUI-xml实战(12)pip可视化管理器

引言 pip命令行工具在平常使用方面确实足够简单&#xff0c;本项目只是作为TinUI多界面开发的示例。 当然&#xff0c;总有人想用GUI版pip&#xff0c;实际上也有。不过现在&#xff0c;我们就来手搓一个基于python和TinUI&#xff08;tkinter&#xff09;的pip可视化管理器。…

Java SpringAOP简介

简介 官方介绍&#xff1a; SpringAOP的全称是&#xff08;Aspect Oriented Programming&#xff09;中文翻译过来是面向切面编程&#xff0c;AOP是OOP的延续&#xff0c;是软件开发中的一个热点&#xff0c;也是Spring框架中的一个重要内容&#xff0c;是函数式编程的一种衍生…

模块化和包管理工具

一&#xff0c;模块化 1.定义 将一个复杂的程序文件依据一定规则&#xff08;规范&#xff09;拆分成多个文件的过程称之为 模块化 其中拆分出的 每个文件就是一个模块 &#xff0c;模块的内部数据是私有的&#xff0c;不过模块可以暴露内部数据以便其他模块使用 2.模块化…

【React Hooks原理 - forwardRef、useImperativeHandle】

概述 上文我们聊了useRef的使用和实现&#xff0c;主要两个用途&#xff1a;1、用于持久化保存 2、用于绑定dom。 但是有时候我们需要在父组件中访问子组件的dom或者属性/方法&#xff0c;而React中默认是不允许父组件直接访问子组件的dom的&#xff0c;这时候就可以通过forwa…

如何通过网络快速搜寻到自己的STM32设备

目录 一、问题概述 二、解决思路 三、代码实现 1.创建任务 2.UDP广播接收 一、问题概述 以前一直用RS232串口修改设备配置信息&#xff0c;但是现场施工人员的232线太细&#xff0c;经常容易断掉&#xff0c;这次准备用网口去修改&#xff0c;遇到了一个问题&#xff0c;…

【简历】惠州某二本学院:前端简历指导,秋招面试通过率为0

注&#xff1a;为保证用户信息安全&#xff0c;姓名和学校等信息已经进行同层次变更&#xff0c;内容部分细节也进行了部分隐藏 简历说明 这是一份25届二本同学&#xff0c;投递前端职位的简历&#xff0c;那么在校招环节二本同学主要针对的还是小公司&#xff0c;这个学校因为…