浙江大学数据结构MOOC-课后习题-第九讲-排序3 Insertion or Heap Sort

news/2024/7/20 10:43:19/文章来源:https://blog.csdn.net/chan1ee/article/details/139255657

题目汇总
浙江大学数据结构MOOC-课后习题-拼题A-代码分享-2024

题目描述

在这里插入图片描述

测试点

在这里插入图片描述

思路分析

和上一题的思路一样,每进行一次迭代,来验证当前序列是否和给定的序列相同

代码展示

#include <cstdlib>
#include <iostream>
#define MAXSIZE 100
typedef int ElementType;void swap(int A[], int i, int j)
{int temp = A[i];A[i] = A[j];A[j] = temp;
}void print(int A[], int N)
{for (int i = 0; i < N; i++){if (i == 0)std::cout << A[i];elsestd::cout << ' ' << A[i];}
}
bool isSame(int A[], int input[], int N)
{for (int i = 0; i < N; i++){if (A[i] != input[i])return false;}return true;
}
bool insertion_Sort(int A[], int input[], int N)
{/* 算法 */int i, j, temp;bool flag = false;for (i = 1; i < N; i++){	temp = A[i];	/* 摸牌 */for (j = i; j > 0 && A[j - 1] > temp; j--)A[j] = A[j - 1];A[j] = temp;if (flag == true){print(A, N);return true;;}if (isSame(A, input, N)){std::cout << "Insertion Sort" << std::endl;flag = true;}}return false;
}void percDown(int A[], int p, int N)
{/* 将N个元素的数组中以A[p]为根的子堆调整为最大堆 */int parent, child;int temp = A[p];for (parent = p; (parent * 2 + 1) < N; parent = child){child = parent * 2 + 1;/* child指向左右孩子中较大者 */if (child != N - 1 && A[child] < A[child + 1])child++;if (temp > A[child]) break;else A[parent] = A[child];}A[parent] = temp;
}
void heap_Sort(int A[], int input[], int N)
{	bool flag = false;	/* 建立大根堆 */for (int i = N - 1; i >= 0; i--)percDown(A, i, N);/* 删除最大值 */for (int i = N - 1; i >= 0; i--){swap(A, 0, i);percDown(A, 0, i);if (flag == true){print(A, N);return;}if (isSame(A, input, N)){std::cout << "Heap Sort" << std::endl;flag = true;}}
}
void check(int A[], int input[], int N)
{int copyA[MAXSIZE];for (int i = 0; i < N; i++)copyA[i] = A[i];if (insertion_Sort(copyA, input, N))return;else{for (int i = 0; i < N; i++)copyA[i] = A[i];heap_Sort(copyA, input, N);return;}
}int main()
{int A[MAXSIZE];int input[MAXSIZE];int N;std::cin >> N;for (int i = 0; i < N; i++)std::cin >> A[i];for (int i = 0; i < N; i++)std::cin >> input[i];check(A, input, N);return 0;
}

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

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

相关文章

中国企业出海,哪些业务需要负载均衡?

国内企业出海的进程正在加速。中国的出海企业剑指跨境电商、社交、游戏、短剧等市场&#xff0c;其中尤其以跨境电商的数据最为突出。据官方数据&#xff0c;2023年我国跨境电商进出口总额达到2.38万亿元&#xff0c;比2016年增长近50倍&#xff0c;占货物贸易总规模的5.7%。 …

电源小白入门学习8——电荷泵电路原理及使用注意事项

电源小白入门学习8——电荷泵电路原理及使用注意事项 电荷泵简介电荷泵原理电荷泵设计过程中需要注意的点fly电容的安秒平衡DC/DC功率转换技术对比 电荷泵简介 电荷泵&#xff08;Charge Pump&#xff09;是一种电路拓扑结构&#xff0c;用于实现电压升压或降压的功能。它通过…

记录深度学习GPU配置,下载CUDA与cuDnn

目标下载: cuda 11.0.1_451.22 win10.exe cudnn-11.0-windows-x64-v8.0.2.39.zip cuda历史版本网址 CUDA Toolkit Archive | NVIDIA Developer 自己下载过11.0.1版本 点击下载local版本,本地安装,有2个多GB,很大,我不喜欢network版本,容易掉线 cuDnn https://developer.nvi…

clickhouse——clickhouse单节点部署及基础命令介绍

clickhouse支持运行在主流的64位CPU架构的linux操作系统之上&#xff0c;可以通过源码编译&#xff0c;预编译压缩包&#xff0c;docker镜像和rpm等多种方式进行安装。 一、单节点部署 1、安装curl工具 yum install -y curl 2、添加clickhouse的yum镜像 curl -s https://pack…

「数据结构」队列

目录 队列的基本概念 队列的实现 头文件queue.h 实现函数接口 1.初始化和销毁 2.出队列和入队列 3.获取队头元素和队尾元素 4.队列长度判空 后记 前言 欢迎大家来到小鸥的博客~ 个人主页&#xff1a;海盗猫鸥 本篇专题&#xff1a;数据结构 多谢大家的支持啦&#xff…

制作Dcoker镜像

文章目录 一、Docker构建镜像的原理1、镜像分层原理2、Docker的镜像结构3、分层存储原理4、构建命令与层的关系5、最终镜像的创建 二、docker commit 构建镜像1、使用场景2、手动制作yum版的nginx镜像2.1、启动一个centos容器&#xff0c;安装好常用的软件以及nginx2.2、关闭ng…

STM32——定时器

一、简介 *定时器可以对输入的时钟进行计数&#xff0c;并在计数值达到设定值时触发中断 *16位计数器、预分频器、自动重装寄存器的时基单元&#xff0c;在72MHz计数时钟下可以实现最大59.65s的定时 *不仅具备基本的定时中断功能&#xff0c;而且还包含内外时钟源选择、输入…

STM32使用ST-LINK下载程序中需要注意的几点

使用keil5的ST-link下载界面 前提是ST-LINK已经连接好&#xff0c;&#xff08;下图中是没有连接ST-link设备&#xff09;&#xff0c;只是为了展示如何查看STlink设备是否连接的方式 下载前一定设置下载完成后自启动 这个虽然不是必须&#xff0c;但对立即看到新程序的现象…

Unity功能——设置Camera,实现玩家被攻击后晃动效果

一、方法说明&#xff1a; 来源&#xff1a;siki学院&#xff1a;Unity项目捕鱼达人&#xff0c;功能学习记录&#xff1b; 效果摘要&#xff1a;通过调整相机移动&#xff0c;视觉感觉玩家面板剧烈晃动&#xff0c;实现被boss攻击时的震动效果。 使用场景说明&#xff1a; …

Python读取Excel表格文件并绘制多列数据的曲线图

本文介绍基于Python语言&#xff0c;读取Excel表格数据&#xff0c;并基于给定的行数范围内的指定列数据&#xff0c;绘制多条曲线图&#xff0c;并动态调整图片长度的方法。 首先&#xff0c;我们来明确一下本文的需求。现有一个.csv格式的Excel表格文件&#xff0c;其第一列为…

【前端学习笔记】HTML基础

HTML 一、HTML介绍1.HTML概念2.文档声明3.字符编码4. HTML标签5. HTML属性 二、标签1.meta标签2.语义标签3.布局标签4.列表5.超链接6.图片7.字符实体8.内联格式9.HTML 表格10.HTML 表单 三、HTML5新特性1. 本地存储2. Cookie3. 语义化标签4.多媒体元素5.表单增强6.Canvas7.SVG …

【算法】位运算算法——判断字符是否唯一

题解&#xff1a;判断字符是否唯一(位运算算法) 目录 1.题目2.题解3.位图参考代码4.细节5.总结 1.题目 题目链接&#xff1a;LINK 2.题解 题解有两种方法&#xff0c; 一是做一个哈希数组&#xff0c;去查重&#xff1b; 二是直接用一个变量每一位来对应表示是否有这个字母…

解决Element组件el-switch在Vue中值的绑定与回显问题

概要 Switch 开关表示两种相互对立的状态间的切换,多用于触发「开/关」。可当一个布尔值进行使用。 问题描述与解决 引入Element组件的switch到Vue中,可以读取switch的值,但如果放在页面中,不能回显上去。 如上图,无论值是"否"还是“是”。都不能正确渲染到页…

Kubernetes部署dashboard

Kubernetes部署dashboard Kubernetes集群安装 鲲鹏arm64架构下安装KubeSphere linux安装部署k8s(kubernetes)和解决遇到的坑 dashboard部署 $ kubectl apply -f https://raw.githubusercontent.com/kubernetes/dashboard/master/src/deploy/recommended/kubernetes-dashbo…

5.28学习总结

java复习总结 hashcode()和equals() hashcode():在Object里这个方法是通过返回地址的整数值来生成哈希值。 equals():在Object里这个方法是通过比较他们的内存地址来确定两个对象是否相同。 运行效率&#xff1a;hashcode的时间复杂度为O(1)&#xff08;因为只要计算一次哈…

生产者延迟消息和重试机制

messageDelayLevel1s 5s 10s 30s 1m 2m 3m 4m 5m 6m 7m 8m 9m 10m 20m 30m 1h 2h 延迟消息级别public PutMessageResult putMessage(final MessageExtBrokerInner msg) {//事务消息处理if (tranType MessageSysFlag.TRANSACTION_NOT_TYPE|| tranType MessageSysFlag.TRANSACT…

Filebeat进阶指南:核心架构与功能组件的深度剖析

&#x1f407;明明跟你说过&#xff1a;个人主页 &#x1f3c5;个人专栏&#xff1a;《洞察之眼&#xff1a;ELK监控与可视化》&#x1f3c5; &#x1f516;行路有良友&#xff0c;便是天堂&#x1f516; 目录 一、引言 1、什么是ELK 2、FileBeat在ELK中的角色 二、Fil…

【机器学习】Pandas中to_pickle()函数的介绍与机器学习中的应用

【机器学习】Pandas中to_pickle()函数的介绍和机器学习中的应用 &#x1f308; 欢迎莅临我的个人主页&#x1f448;这里是我深耕Python编程、机器学习和自然语言处理&#xff08;NLP&#xff09;领域&#xff0c;并乐于分享知识与经验的小天地&#xff01;&#x1f387; &#…

卧式混料机:混合设备的智慧之选

卧式混料机&#xff0c;顾名思义&#xff0c;是一种采用卧式结构的混合设备。它的设计精巧&#xff0c;结构紧凑&#xff0c;不仅占用空间小&#xff0c;而且操作简便&#xff0c;维护方便。与传统的立式混料机相比&#xff0c;卧式混料机在混合效率、混合均匀度以及物料适应性…

Android环境下Mesa初始化流程重学习之eglCreateContext

Mesa初始化流程重学习之eglCreateContext 引言 没有啥好说的了&#xff0c;直接上手撸代码&#xff01;总得找点事情干不是!我打工我快乐&#xff01;我奋斗&#xff0c;我快乐&#xff01; 一. 核心结构体之间的关联 二. eglCreateContext流程分析 eglCreateContext(...)//s…