【数据结构——内排序】二路归并排序(头歌实践教学平台习题)【合集】

目录😋

任务描述

测试说明

我的通关代码:

测试结果:


任务描述

本关任务:实现二路归并算法。

测试说明

平台会对你编写的代码进行测试:

测试输入示例:
11
18 2 20 34 12 32 6 16 5 8 1 
(说明:第一行是元素个数,第二行是待排序的原始关键字数据。)

输出示例:
排序前:18 2 20 34 12 32 6 16 5 8 1 
第1趟归并:2 18 20 34 12 32 6 16 5 8 1 
第2趟归并:2 18 20 34 6 12 16 32 1 5 8 
第3趟归并:2 6 12 16 18 20 32 34 1 5 8 
第4趟归并:1 2 5 6 8 12 16 18 20 32 34 
排序后:1 2 5 6 8 12 16 18 20 32 34 

开始你的任务吧,祝你成功!


我的通关代码:

#include <malloc.h>
#include <stdio.h>

#define MAXL 100     //最大长度
typedef int KeyType; //定义关键字类型为int
typedef char InfoType;

typedef struct {
  KeyType key;   //关键字项
  InfoType data; //其他数据项,类型为InfoType
} RecType;       //查找元素的类型

int count = 1; //全局变量,记录第几趟归并

void CreateList(RecType R[], KeyType keys[], int n) //创建顺序表
{
  for (int i = 0; i < n; i++) // R[0..n-1]存放排序记录
    R[i].key = keys[i];
}
void DispList(RecType R[], int n) //输出顺序表
{
  for (int i = 0; i < n; i++)
    printf("%d ", R[i].key);
  printf("\n");
}

//一次归并:将两个有序表R[low..mid]和R[mid+1..high]归并为一个有序表R[low..high]中
void Merge(RecType R[], int low, int mid, int high) {
  /********** Begin *********/
  RecType *R1 = (RecType *)malloc((high - low + 1) * sizeof(RecType));
  int i = low, j = mid + 1, k = 0;
  while (i <= mid && j <= high) {
    if (R[i].key <= R[j].key)
      R1[k++] = R[i++];
    else
      R1[k++] = R[j++];
  }
  while (i <= mid)
    R1[k++] = R[i++];
  while (j <= high)
    R1[k++] = R[j++];
  for (k = 0, i = low; i <= high; i++, k++)
    R[i] = R1[k];
  free(R1);
  /********** End **********/
}

void MergePass(RecType R[], int length, int n) //实现一趟归并
{
  /********** Begin *********/
  int i;
  for (i = 0; i + 2 * length - 1 < n; i += 2 * length)
    Merge(R, i, i + length - 1, i + 2 * length - 1);
  if (i + length - 1 < n)
    Merge(R, i, i + length - 1, n - 1);
  /********** End **********/
}

void MergeSort(RecType R[], int n) //二路归并排序算法
{
  /********** Begin *********/
  int length = 1;
  printf("排序前:");
  DispList(R, n);
  while (length < n) {
    MergePass(R, length, n);
    printf("第%d趟归并:", count++);
    DispList(R, n);
    length *= 2;
  }
  printf("排序后:");
  DispList(R, n);
  /********** End **********/
}

int main() {
  /********** Begin *********/
  int n;
  scanf("%d", &n);
  KeyType keys[MAXL];
  RecType R[MAXL];
  for (int i = 0; i < n; i++)
    scanf("%d", &keys[i]);
  CreateList(R, keys, n);
  MergeSort(R, n);
  /********** End **********/
  return 0;
}

测试结果:


在这里插入图片描述

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

东方明珠生成式人工智能媒体融合创新平台荣获AI Cloud轻量云典型案例

近日&#xff0c;由全球数字经济大会组委会主办&#xff0c;中国信息通信研究院&#xff08;以下简称“信通院”&#xff09;、中国通信企业协会承办的2024全球数字经济大会云AI计算国际合作论坛在北京成功召开。会上隆重发布了2024年“AI Cloud助力大模型场景化和工程化落地”…

高阶数据结构--B树B+树实现原理B树模拟实现--Java

目录 一、B-树概念 二、B-树插入分析 1.用序列{53, 139, 75, 49, 145, 36, 101}构建B树的过程如下&#xff1a; 2.插入过程总结 三、B树插入实现 四、B树 1.B树概念 2.B树的特性 五、B树应用 1.索引 2.Mysql索引 3.InnoDB 一、B-树概念 1970 年&#xff0c; R.Bayer 和…

优选算法——分治(快排)

1. 颜色分类 题目链接&#xff1a;75. 颜色分类 - 力扣&#xff08;LeetCode&#xff09; 题目展示&#xff1a; 题目分析&#xff1a;本题其实就要将数组最终分成3块儿&#xff0c;这也是后面快排的优化思路&#xff0c;具体大家来看下图。 这里我们上来先定义了3个指针&…

Edge SCDN的独特优势有哪些?

强大的边缘计算能力 Edge SCDN&#xff08;边缘安全加速&#xff09;是酷盾安全推出的边缘集分布式 DDoS 防护、CC 防护、WAF 防护、BOT 行为分析为一体的安全加速解决方案。通过边缘缓存技术&#xff0c;智能调度使用户就近获取所需内容&#xff0c;为用户提供稳定快速的访问…

「Mac玩转仓颉内测版45」小学奥数篇8 - 排列组合计算

本篇将通过 Python 和 Cangjie 双语讲解如何计算排列与组合。这道题目旨在让学生学会使用排列组合公式解决实际问题&#xff0c;并加深对数学知识和编程逻辑的理解。 关键词 小学奥数Python Cangjie排列与组合 一、题目描述 编写一个程序&#xff0c;计算从 n 个不同元素中取…

基于Q-Learning的机器人栅格地图路径规划,可以更改地图大小及起始点,可以自定义障碍物,MATLAB代码

基于Q-learning算法的栅格地图路径规划是一种利用强化学习技术来解决路径规划问题的方法。 状态空间定义&#xff1a;在路径规划任务中&#xff0c;状态通常代表机器人或智能体在环境中的位置。状态空间可以是离散的&#xff0c;如网格地图上的特定位置。 动作空间定义&#x…

中电金信携手中远海科,共启贸易金融数智新篇章

在数智化转型成为驱动经济社会高质量发展的新引擎背景下&#xff0c;“数智方案”栏目聚焦金融等国计民生重点行业场景&#xff0c;依托中电金信“源启筑基咨询引领应用重构”的产品及服务体系&#xff0c;输出市场洞察和行业解决方案、应用案例&#xff0c;旨在全面推动行业IT…

抗DDOS设备

0x00 定义: 抗DDOS设备顾名思义&#xff0c;就是防御DDoS攻击的设备&#xff0c;通常包含三个部分&#xff1a;检测中心、清洗中心和管理中心 检测中心主要负责对流量进行检测&#xff0c;发现流量异常后上报管理中心&#xff0c;由管理中心下发引流策略至清洗中心&#xff0…

游戏引擎学习第42天

仓库: https://gitee.com/mrxiao_com/2d_game 简介 目前我们正在研究的内容是如何构建一个基本的游戏引擎。我们将深入了解游戏开发的每一个环节&#xff0c;从最基础的技术实现到高级的游戏编程。 角色移动代码 我们主要讨论的是角色的移动代码。我一直希望能够使用一些基…

Node一、fs 模块、path 模块、端口号、 http 模块、

一、Node.js了解 Node.js是一个跨平台JavaScript运行环境&#xff0c;使开发者可以搭建服务器端的JavaScript应用程序。 概念&#xff1a;使用 Node.js 编写后端程序 / 支持前端工程化 ✓ 后端程序&#xff1a;提供接口和数据&#xff0c;网页资源等 ✓ 前端工程化 &#x…

游戏引擎学习第44天

仓库: https://gitee.com/mrxiao_com/2d_game 向量数学的重要性 矢量数学非常重要&#xff0c;因为 它在某种程度上类似于将C和C视为高于汇编语言的语言&#xff0c;从而使得我们能够以略高的层次思考问题&#xff0c;同时保留大部分性能好处和直接访问的类型。这种思维方式就…

【算法day13】二叉树:递归与回溯

题目引用 找树左下角的值路径总和从中序与后序遍历构造二叉树 今天就简简单单三道题吧~ 1. 找到树左下角的值 给定一个二叉树的 根节点 root&#xff0c;请找出该二叉树的 最底层 最左边 节点的值。 假设二叉树中至少有一个节点。 示例 1: 输入: root [2,1,3] 输出: 1 我们…

MindSearch深度解析实践

1. 课程内容 1.1 MindSearch 简介 MindSearch 是一个开源的 AI 搜索引擎框架&#xff0c;具有与 Perplexity.ai Pro 相同的性能。我们可以轻松部署它来构建自己的专属搜索引擎&#xff0c;可以基于闭源的LLM&#xff08;如GPT、Claude系列&#xff09;&#xff0c;也可以使用…

【数据结构进阶】AVL树深度剖析 + 实现(附源码)

&#x1f31f;&#x1f31f;作者主页&#xff1a;ephemerals__ &#x1f31f;&#x1f31f;所属专栏&#xff1a;数据结构 目录 前言 一、AVL树的概念 二、AVL树底层解析及实现 1. 节点的定义 2. 接口声明 3. AVL树的插入 3.1 更新平衡因子 3.2 旋转&#xff08;重点…

黑马商城微服务复习(6)

MQ高级 1. 消息可靠性2. 发送者的可靠性1. 发送者问题2. 生产者重试机制3. 生产者确认机制4. MQ可靠性5. 消费者的可靠性 3. 延迟消息1. 定义2. 死信交换机 1. 消息可靠性 发送消息时丢失&#xff1a; 生产者发送消息时连接MQ失败生产者发送消息到达MQ后未找到Exchange生产者发…

深度优先搜索(DFS)与回溯法:从全排列到子集问题的决策树与剪枝优化

文章目录 前言&#x1f384;一、全排列✨核心思路✨实现步骤✨代码✨时间和空间复杂度&#x1f381;1. 时间复杂度&#x1f381;2. 空间复杂度 &#x1f384;二、子集✨解法一&#xff1a;逐位置决策法&#x1f381;步骤分析&#x1f381;运行示例&#x1f381;代码 ✨解法二&a…

STM32--中断

中断 中断向量表 定义一段固定的内存&#xff0c;以4字节对齐&#xff0c;存放各个中断服务函数程序的首地址。定义在启动文件中。 中断相关寄存器 内核中断不经过中断使能、除能寄存器。 中断优先级 1、抢占优先级&#xff1a;高高抢占优先级可以打断正在执行的低抢占优先…

AUTOSAR 汽车开放系统架构

AUTOSAR 官网 AUTOMOTIVE OPEN SYSTEM ARCHITECTURE AUTOSAR (AUTomotive Open System ARchitecture) is a global partnership of leading companies in the automotive and software industry to develop and establish the standardized software framework and open E/E …

《计算机视觉:瓶颈之辩与未来之路》

一、计算机视觉的崛起 计算机视觉是使用计算机模仿人类视觉系统的科学&#xff0c;让计算机拥有类似人类提取、处理、理解和分析图像以及图像序列的能力。它是一个多学科交叉的领域&#xff0c;与机器视觉、图像处理、人工智能、机器学习等领域密切相关。 计算机视觉行业可分为…

Vue 集成地图

电子地图应用广泛&#xff1a; 网约车 : 在网约车 场景中实现 准定位 、导航 、司乘同显 &#xff0c;精准计费 智慧物流、生活服务等&#xff0c;本专题课程囊括各类应用场景 学习 电子地图解决方案&#xff0c;满足学员工作学习各类需求。 基础知识 学习 集成 地图之前需…