数据结构OJ实验15-插入排序与交换排序
A. DS内排—直插排序
题目描述
给定一组数据,使用直插排序完成数据的升序排序。
--程序要求--
若使用C++只能include一个头文件iostream;若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件,不看代码,作0分处理
不允许使用第三方对象或函数实现本题的要求
输入
数据个数n,n个数据
输出
直插排序的每一趟排序结果
样例查看模式
正常显示查看格式
输入样例1
7 34 23 677 2 1 453 3
输出样例1
23 34 677 2 1 453 3\n
23 34 677 2 1 453 3\n
2 23 34 677 1 453 3\n
1 2 23 34 677 453 3\n
1 2 23 34 453 677 3\n
1 2 3 23 34 453 677\n
AC代码
#include<iostream>
using namespace std;
const int N = 1e5;
int a[N];
int n;
void insert_sort()
{for (int i = 1; i < n; i++){int t = a[i];int j;for (j = i - 1; j >= 0; j--){if (a[j] > t){a[j + 1] = a[j];}else break;}a[j+1] = t;for (j = 0; j < n; j++){cout << a[j];if (j != n - 1)cout << " ";else cout << endl;}}
}
int main()
{cin >> n;for (int i = 0; i < n; i++){cin >> a[i];}insert_sort();return 0;
}
B. DS排序--希尔排序
题目描述
给出一个数据序列,使用希尔排序算法进行降序排序。
间隔gap使用序列长度循环除2直到1
输入
第一行输入t,表示有t个测试示例
第二行输入n,表示第一个示例有n个数据(n>1)
第三行输入n个数据,都是正整数,数据之间用空格隔开
以此类推
输出
对每组测试数据,输出每趟排序结果。不同组测试数据间用空行分隔。
样例查看模式
正常显示查看格式
输入样例1
2\n
6\n
111 22 6 444 333 55\n
8\n
77 555 33 1 444 77 666 2222\n
输出样例1
444 333 55 111 22 6\n
444 333 111 55 22 6\n
\n
444 555 666 2222 77 77 33 1\n
666 2222 444 555 77 77 33 1\n
2222 666 555 444 77 77 33 1\n
AC代码
#include<iostream>
using namespace std;
int n;
const int N = 1e5;
int a[N];
void shell_sort(int gap)
{for (int i = gap; i < n; i ++)//每一个元素{int t = a[i];int j;for (j = i - gap; j >= 0; j -= gap){if (a[j] < t){a[j + gap] = a[j];}else break;}a[j + gap] = t;}
}
int main()
{int t;cin >> t;while (t--){cin >> n;for (int i = 0; i < n; i++){cin >> a[i];}int gap = n;while (gap != 1){gap /= 2;shell_sort(gap);for (int j = 0; j < n; j++){cout << a[j];if (j != n - 1)cout << " ";else cout << endl;}}if (t)cout << endl;}return 0;
}
C. 冒泡排序
题目描述
给定一个包含从0到n-1各一次的数组,若使用冒泡排序将其排为升序,问其中需要进行多少次交换
输入
测试数据有多组,
每组由两行组成:第一行包含正整数n(n <= 5000); 下一行包含从0到n-1的n个整数的序列。
输出
对于每组测试数据,
输出交换次数
样例查看模式
正常显示查看格式
输入样例1
10\n
1 3 6 9 0 8 5 7 4 2
输出样例1
22
AC代码
#include<iostream>
using namespace std;
int n;
const int N = 1e5;
int a[N];
void pop_sort()
{int ans = 0;for (int i = 0; i < n - 1; i++){for (int j = i + 1; j < n; j++){if (a[j] < a[i])swap(a[j], a[i]),ans++;}}cout << ans << endl;
}
int main()
{while (cin>>n){for (int i = 0; i < n; i++){cin >> a[i];}pop_sort();}return 0;
}
D. DS排序--快速排序
题目描述
给出一个数据序列,使用快速排序算法进行从小到大的排序
--程序要求--
若使用C++只能include一个头文件iostream;若使用C语言只能include一个头文件stdio
程序中若include多过一个头文件,不看代码,作0分处理
不允许使用第三方对象或函数实现本题的要求
输入
第一行输入t,表示有t个测试示例
第二行输入n,表示第一个示例有n个数据
第三行输入n个数据,都是正整数,数据之间用空格隔开
以此类推
输出
每组测试数据,输出每趟快排的结果,即每次排好一个数字结果(长度为1的子序列,不用排,不用输出)。不同测试数据间用空行分隔。
样例查看模式
正常显示查看格式
输入样例1
2\n
6\n
111 22 6 444 333 55\n
8\n
77 555 33 1 444 77 666 2222\n
输出样例1
55 22 6 111 333 444\n
6 22 55 111 333 444\n
6 22 55 111 333 444\n
6 22 55 111 333 444\n
\n
1 33 77 555 444 77 666 2222\n
1 33 77 555 444 77 666 2222\n
1 33 77 77 444 555 666 2222\n
1 33 77 77 444 555 666 2222\n
1 33 77 77 444 555 666 2222\n
AC代码
#include<iostream>
using namespace std;
int n;
const int N = 1e5;
int a[N];
void quick_sort(int low, int high)
{int i = low, j = high;if (i >= j)return;int t = a[low];while (i != j){while (a[j] >= t && i < j)j--;if (i >= j)break;a[i] = a[j];i++;while (a[i] <= t && i < j)i++;if (i < j){swap(a[i], a[j]);}}a[i] = t;//重合for (int k= 1; k <= n; k++){cout << a[k];if (k != n)cout << " ";else cout << endl;}quick_sort(low, i - 1);quick_sort(i + 1, high);
}
int main()
{int t;cin >> t;while (t--){cin >> n;for (int i = 1; i <= n; i++){cin >> a[i];}quick_sort(1, n);if(t)cout<<endl;}return 0;
}
E. 大数据量的冒泡排序 (计次数)
题目描述
给定一个包含从0到n-1各一次的数组,若使用冒泡排序将其排为升序,问其中需要进行多少次交换
输入
测试数据有多组,
每组由两行组成:第一行包含正整数n(n <= 5000); 下一行包含从0到n-1的n个整数的序列。
输出
对于每组测试数据,输出一行,输出交换总次数
样例查看模式
正常显示查看格式
输入样例1
10\n
1 3 6 9 0 8 5 7 4 2\n
输出样例1
22\n
AC代码
#include<iostream>
using namespace std;
int n;
const int N = 1e5;
int a[N];
void pop_sort()
{int ans = 0;for (int i = 0; i < n - 1; i++){for (int j = i + 1; j < n; j++){if (a[j] < a[i])swap(a[j], a[i]),ans++;}}cout << ans << endl;
}
int main()
{while (cin>>n){for (int i = 0; i < n; i++){cin >> a[i];}pop_sort();}return 0;
}
F. 与零交换
题目描述
将 { 0, 1, 2, ..., N-1 } 的任意一个排列进行排序并不困难,这里加一点难度,要求你只能通过一系列的 Swap(0, *) —— 即将一个数字与 0 交换 —— 的操作,将初始序列增序排列。例如对于初始序列 { 4, 0, 2, 1, 3 },我们可以通过下列操作完成排序:
- Swap(0, 1) ⟹ { 4, 1, 2, 0, 3 }
- Swap(0, 3) ⟹ { 4, 1, 2, 3, 0 }
- Swap(0, 4) ⟹ { 0, 1, 2, 3, 4 }
本题要求你找出将前 N 个非负整数的给定排列进行增序排序所需要的最少的与 0 交换的次数。
输入
输入在第一行给出正整数 N (≤105);随后一行给出{ 0, 1, 2, ..., N-1 } 的一个排列。数字间以空格分隔。
输出
在一行中输出将给定序列进行增序排序所需要的最少的与 0 交换的次数。
样例查看模式
正常显示查看格式
输入样例1
10\n
3 5 7 2 6 4 9 0 8 1
输出样例1
9
AC代码
#include<iostream>
using namespace std;
int n;
const int N = 1e5;
int a[N];
bool st[N];
int ans;
int main()
{cin >> n;for (int i = 0; i < n; i++)cin >> a[i];for (int i = 0; i < n; i++){if (!st[i] && a[i] != i){bool flag = 0;int idx = i;int cnt = 0;while (!st[idx]){if (a[idx] == 0)flag = 1;st[idx] = 1;idx = a[idx];cnt++;}if (flag)ans += (cnt - 1);else ans += (cnt + 1);}else st[i] = 1;}cout << ans << endl;return 0;
}
相关文章:
数据结构OJ实验15-插入排序与交换排序
A. DS内排—直插排序 题目描述 给定一组数据,使用直插排序完成数据的升序排序。 --程序要求-- 若使用C只能include一个头文件iostream;若使用C语言只能include一个头文件stdio 程序中若include多过一个头文件,不看代码,作0分…...

鹿目标检测数据集VOC格式500张
鹿,一种优雅而神秘的哺乳动物,以其优美的外形和独特的生态习性而备受人们的喜爱。 鹿的体型通常中等,四肢细长,身体线条流畅。它们的头部较小,耳朵大而直立,眼睛明亮有神。鹿的毛色因品种而异,…...

静态网页设计——电影推荐网(HTML+CSS+JavaScript)
前言 声明:该文章只是做技术分享,若侵权请联系我删除。!! 感谢大佬的视频: https://www.bilibili.com/video/BV1NK411x7oK/?vd_source5f425e0074a7f92921f53ab87712357b 使用技术:HTMLCSSJS(…...
ARM CCA机密计算架构软件栈简介
本博客描述了Arm机密计算架构(Arm CCA)的固件和软件组件。 在这篇博客中,您将学到如何: 列出组成Arm CCA软件栈的组件集了解Arm CCA引入新软件组件的原因了解监视器和领域管理监视器(RMM)的角色了解如何创建和管理领域1.1 开始之前 我们假设您熟悉AArch64异常模型、AAr…...

C#编程-使用集合
使用集合 您学习了如何使用数组来有效地存储和操作相似类型额数据。但是,以下限制于数组的使用相关联: 您必须在声明时定义数组的大小。您必须编写代码以对数组执行标准操作,如排序。让我们思考一个示例。假设您想要存储在组织工作的五个雇员的姓名。您可以使用以下语句来声…...
linux 设备模型之设备
在最低层, Linux 系统中的每个设备由一个 struct device 代表: struct device { struct device *parent; struct kobject kobj; char bus_id[BUS_ID_SIZE]; struct bus_type *bus; struct device_driver *driver; void *driver_data; void (*release)(struct device *dev); /* …...
电源滤波可采用 RC、LC、π 型滤波。电源滤波建议优选磁珠,然后才是电感。同时电阻、电感和磁珠必须考虑其电阻产生的压降。
电源滤波是为了减少电源中的噪声和干扰,确保电子设备正常工作。RC、LC、π 型滤波是常用的电源滤波器结构,其选择主要取决于需要滤波的频率范围和所需的滤波效果。 RC滤波器是由电阻和电容组成,适用于高频噪声的滤波。当电流通过电容时,电容会阻止高频噪声信号的通过,起到…...

STM32通用定时器-输入捕获-脉冲计数
一、知识点 编码器 两相编码器(正交编码器):两相编码器由 A 相和 B 相组成,相位差为 90 度。当旋转方向为顺时针时,A 相先变化,然后 B 相变化;当旋转方向为逆时针时,B 相先变化…...
Flutter GetX 之 路由管理
路由管理是插件GetX常用功能之一,为什么说之一呢?因为GetX的功能远不止路由管理这么简单。 GetX的重要功能如下: 1、路由管理2、状态管理3、国际化4、主题5、GetUtil工具6、dialog 弹框7、snackbar 其实上面功能介绍的还是不够详细ÿ…...

基于单片机的农田灌溉系统(论文+源码)
1.系统设计 本系统主要实现如下目标: 1.可以实时监测土壤湿度; 2.土壤湿度太低时,进行浇水操作; 3.可以按键设置湿度的触发阈值; 4. 可以实现远程操控 5.可以实现手…...

分布式缓存 -- 基础
负载均衡 Ribbon 服务间通信的负载均衡工具,提供完善的超时重试机制 客户端的负载均衡器:在客户端将各个服务的信息拿到,在客户端本地做到请求的均衡分配 Ribbon 提供 LoadBalanced 注解,外搭配RestTemplate来做客户端的负载均衡…...
云计算复习笔记--期末
1、云计算的定义和本质: 云计算是一种按使用量付费的模式。云计算是分布式计算的一种。通过计算机网络(多指因特网)形成的计算能力极强的系统,可存储、集合相关资源并可按需配置,向用户提供个性化服务。 2、云计算服…...
【WPF.NET开发】WPF中的焦点
本文内容 键盘焦点逻辑焦点键盘导航以编程方式导航焦点焦点事件 在 WPF 中,有两个与焦点有关的主要概念:键盘焦点和逻辑焦点。 键盘焦点指接收键盘输入的元素,而逻辑焦点指焦点范围中具有焦点的元素。 本概述详细介绍了这些概念。 对于创建…...

【计算机设计大赛作品】豆瓣电影数据挖掘可视化—信息可视化赛道获奖项目深入剖析【可视化项目案例-22】
文章目录 一.【计算机设计大赛作品】豆瓣电影数据挖掘可视化—信息可视化赛道获奖项目深入剖析【可视化项目案例-22】1.1 项目主题:豆瓣电影二.代码剖析2.1 项目效果展示2.2 服务端代码剖析2.3 数据分析2.4 数据评分三.寄语四.本案例完整源码下载一.【计算机设计大赛作品】豆瓣…...

VS2019启动编辑并继续不起作用(.NET)
直接上方案 1)请确保您取消选中工具>选项>调试>常规下的选项:使用托管兼容模式和要求源文件与原始版本完全匹配。如下图: 2)请先取消选中编辑并继续选项,然后关闭您的旧解决方案,删除解决方案文件夹中的.vs隐藏文件夹&a…...
FFmpeg处理音视频的常用API及一般流程
FFmpeg是一个开源的音视频处理库,提供了丰富的API用于音视频的编解码、转码、过滤、播放等操作。 一、使用FFmpeg API解码涉及到的函数及一般流程如下: 1. av_register_all(): 注册所有的编解码器和格式。 av_register_all(); 2. avformat_open_inpu…...

Kotlin协程学习之-01
由于协程需要支持挂起、恢复、因此对于挂起点的状态保存就显得机器关键。类似的,线程会因为CPU调度权的切换而被中断,它的中断状态会保存在调用栈当中,因而协程的实现也按照是否开辟相应的调用栈存在以下两种类型: 有栈协程&…...
214.【2023年华为OD机试真题(C卷)】测试用例执行计划(排序题-JavaPythonC++JS实现)
🚀点击这里可直接跳转到本专栏,可查阅顶置最新的华为OD机试宝典~ 本专栏所有题目均包含优质解题思路,高质量解题代码(Java&Python&C++&JS分别实现),详细代码讲解,助你深入学习,深度掌握! 文章目录 一. 题目-测试用例执行计划二.解题思路三.题解代码Pytho…...

数一下 1到 100 的所有整数中出现多少个数字9并输出这些数字
分析: 我们知道 1-100的整数 i 中,9会出现在十位和个位上,数9出现的次数可以通过以下来实现: 个位是9 // i % 10得到整数 i 个位上的数十位是9 // i / 10得到整数 i 除了个位数的数字 这也是做这道题之后,我们需要…...

07. HTTP接口请求重试怎么处理?
目录 1、前言 2、实现方式 2.1、循环重试 2.2、递归重试 2.3、Spring Retry 2.4、Resilience4j 2.5、http请求网络工具内置重试方式 2.6、自定义重试工具 2.7、并发框架异步重试 2.8、消息队列 3、小结 1、前言 HTTP接口请求重试是指在请求失败时,再次发…...

【Axure高保真原型】引导弹窗
今天和大家中分享引导弹窗的原型模板,载入页面后,会显示引导弹窗,适用于引导用户使用页面,点击完成后,会显示下一个引导弹窗,直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

【kafka】Golang实现分布式Masscan任务调度系统
要求: 输出两个程序,一个命令行程序(命令行参数用flag)和一个服务端程序。 命令行程序支持通过命令行参数配置下发IP或IP段、端口、扫描带宽,然后将消息推送到kafka里面。 服务端程序: 从kafka消费者接收…...
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以?
Golang 面试经典题:map 的 key 可以是什么类型?哪些不可以? 在 Golang 的面试中,map 类型的使用是一个常见的考点,其中对 key 类型的合法性 是一道常被提及的基础却很容易被忽视的问题。本文将带你深入理解 Golang 中…...

工业安全零事故的智能守护者:一体化AI智能安防平台
前言: 通过AI视觉技术,为船厂提供全面的安全监控解决方案,涵盖交通违规检测、起重机轨道安全、非法入侵检测、盗窃防范、安全规范执行监控等多个方面,能够实现对应负责人反馈机制,并最终实现数据的统计报表。提升船厂…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...

C# 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)
前言: 双亲委派机制对于面试这块来说非常重要,在实际开发中也是经常遇见需要打破双亲委派的需求,今天我们一起来探索一下什么是双亲委派机制,在此之前我们先介绍一下类的加载器。 目录 编辑 前言: 类加载器 1. …...

Ubuntu系统多网卡多相机IP设置方法
目录 1、硬件情况 2、如何设置网卡和相机IP 2.1 万兆网卡连接交换机,交换机再连相机 2.1.1 网卡设置 2.1.2 相机设置 2.3 万兆网卡直连相机 1、硬件情况 2个网卡n个相机 电脑系统信息,系统版本:Ubuntu22.04.5 LTS;内核版本…...

从物理机到云原生:全面解析计算虚拟化技术的演进与应用
前言:我的虚拟化技术探索之旅 我最早接触"虚拟机"的概念是从Java开始的——JVM(Java Virtual Machine)让"一次编写,到处运行"成为可能。这个软件层面的虚拟化让我着迷,但直到后来接触VMware和Doc…...
多元隐函数 偏导公式
我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式,给定一个隐函数关系: F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 🧠 目标: 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z、 …...