当前位置: 首页 > news >正文

【C/C++ 01】初级排序算法

排序算法通常是针对数组或链表进行排序,在C语言中,需要手写排序算法完成对数据的排序,排序规则通常为升序或降序(本文默认为升序),在C++中,<algorithm>头文件中已经封装了基于快排算法的 std::sort() 函数,但是快速排序是不稳定的排序算法,于是<algorithm>中还包含了 stable_sort() 函数,即保留了等值元素的相对顺序。

稳定性:通常,在排序算法中,稳定性是指如果两个元素在原始数组中的相对顺序保持不变,则在排序后它们的相对顺序也应该保持不变。换句话说,如果有两个相等的元素,它们的位置在排序之前是 a 和 b,且 a 在 b 的前面,那么在排序后,a 仍然应该在 b 的前面。

在进行排序算法之前,先定义一个用于交换元素位置的函数:

void Swap(int* a, int* b)
{int tmp = *a;*a = *b;*b = tmp;
}

一、冒泡排序(Bubble Sort)

冒泡排序的核心算法是暴力求解思维,是指将所有元素都相互比较一次,若靠前的数比靠后的数大,则将两个数交换位置。

  • 排序对象:数组
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)
  • 是否稳定:是
void BubbleSort(int* arr, int n)
{for (int i = 0; i < n; ++i){for (int j = 0; j < n - i - 1; ++j){if (arr[j] > arr[j + 1]){Swap(&arr[j], &arr[j + 1]);}}}
}

二、插入排序(Insert Sort)

插入排序的核心算法是将当前遍历到的地方的末尾数据往前比较,找到合适的位置进行插入,直到遍历到最后一个数据。

  • 排序对象:数组、链表
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)
  • 是否稳定:是
void InsertSort(int* arr, int n)
{int i = 1;for (; i < n; ++i){int j = i;int end = arr[j];while (j > 0 && arr[j - 1] > end){arr[j] = arr[j - 1];--j;}arr[j] = end;}
}

三、选择排序(Select Sort)

选择排序的算法核心是找到数组的最大值和最小值,将其和遍历数组的左右端进行交换,然后左端右移、右端左移。简易版的选择排序算法会只找一个最值进行交换。

  • 排序对象:数组、链表
  • 时间复杂度:O(n^2)
  • 空间复杂度:O(1)
  • 是否稳定:否
void SelectSort(int* arr, int n)
{int left = 0;int right = n - 1;while (left < right){int iMin = left; int iMax = right;for (int i = left; i <= right; ++i){if (arr[i] < arr[iMin])iMin = i;if (arr[i] > arr[iMax])iMax = i;} Swap(&arr[left], &arr[iMin]);if (left == iMax)iMax = iMin;Swap(&arr[right], &arr[iMax]);++left;--right;}
}

相关文章:

【C/C++ 01】初级排序算法

排序算法通常是针对数组或链表进行排序&#xff0c;在C语言中&#xff0c;需要手写排序算法完成对数据的排序&#xff0c;排序规则通常为升序或降序&#xff08;本文默认为升序&#xff09;&#xff0c;在C中&#xff0c;<algorithm>头文件中已经封装了基于快排算法的 st…...

Android Settings 显示电池点亮百分比

如题&#xff0c;Android 原生 Settings 里有个 电池电量百分比 的选项&#xff0c;打开后电池电量百分比会显示在状态栏。 基于 Android 13 &#xff0c; 代码在 ./packages/apps/Settings/src/com/android/settings/display/BatteryPercentagePreferenceController.java &am…...

Windows记事本不显示下划线的原因及解决方法

最近使用Windows 记事本敲代码发现一个问题&#xff1a;代码中的下划线无法显示&#xff01;&#xff01;&#xff01;(字体为“微软雅黑”、字体大小为11下&#xff0c;代码中的下划线无法显示。当然每个人情况可能不同) 在 Windows 记事本中&#xff0c;下划线可能会因为 字体…...

嵌入式软件工程师面试题——2025校招社招通用(C/C++)(四十六)

说明&#xff1a; 面试群&#xff0c;群号&#xff1a; 228447240面试题来源于网络书籍&#xff0c;公司题目以及博主原创或修改&#xff08;题目大部分来源于各种公司&#xff09;&#xff1b;文中很多题目&#xff0c;或许大家直接编译器写完&#xff0c;1分钟就出结果了。但…...

【学网攻】 第(13)节 -- 动态路由(OSPF)

系列文章目录 目录 系列文章目录 文章目录 前言 一、动态路由是什么&#xff1f; 二、实验 1.引入 实验拓扑图 实验配置 实验验证 总结 文章目录 【学网攻】 第(1)节 -- 认识网络【学网攻】 第(2)节 -- 交换机认识及使用【学网攻】 第(3)节 -- 交换机配置聚合端口【学…...

Asp.Net Core 获取应用程序相关目录

在ASP.NET Core中&#xff0c;可以通过以下三种方式获取应用程序所在目录&#xff1a; 1、使用AppContext.BaseDirectory属性&#xff1a; string appDirectory AppContext.BaseDirectory; 例如&#xff1a;D:\后端项目\testCore\test.WebApi\bin\Debug\net6.0\ 2、使用…...

文献速递:人工智能医学影像分割--- 深度学习分割骨盆骨骼:大规模CT数据集和基线模型

文献速递&#xff1a;人工智能医学影像分割— 深度学习分割骨盆骨骼&#xff1a;大规模CT数据集和基线模型 我们为大家带来人工智能技术在医学影像分割上的应用文献。 人工智能在医学影像分析中发挥着至关重要的作用&#xff0c;尤其体现在图像分割技术上。这项技术的目的是准…...

PaddleNLP的简单使用

1 介绍 PaddleNLP是一个基于PaddlePaddle深度学习平台的自然语言处理&#xff08;NLP&#xff09;工具库。 它提供了一系列用于文本处理、文本分类、情感分析、文本生成等任务的预训练模型、模型组件和工具函数。 PaddleNLP有统一的应用范式&#xff1a;通过 paddlenlp.Task…...

2. MySQL 多实例

重点&#xff1a; MySQL 的 三种安装方式&#xff1a;包安装&#xff0c;二进制安装&#xff0c;源码编译安装。 MySQL 的 基本使用 MySQL 多实例 DDLcreate alter drop DML insert update delete DQL select 2.5&#xff09;通用 二进制格式安装 MySQL 2.5.1&#xff…...

两个五层决策树和一个十层决策树的区别

随机森林的弹性: 随机森林中的多个决策树是相互独立构建的&#xff0c;因此两个五层决策树和一个十层决策树之间的区别可能在于它们对训练数据的不同学习。这种弹性有助于模型更好地适应不同的数据模式。 过拟合风险: 十层决策树可能更容易过拟合训练数据&#xff0c;尤其是在数…...

案例分析技巧-软件工程

一、考试情况 需求分析&#xff08;※※※※&#xff09;面向对象设计&#xff08;※※&#xff09; 二、结构化需求分析 数据流图 数据流图的平衡原则 数据流图的答题技巧 利用数据平衡原则&#xff0c;比如顶层图的输入输出应与0层图一致补充实体 人物角色&#xff1a;客户、…...

如何使用docker compose安装APITable并远程访问登录界面

文章目录 前言1. 部署APITable2. cpolar的安装和注册3. 配置APITable公网访问地址4. 固定APITable公网地址 正文开始前给大家推荐个网站&#xff0c;前些天发现了一个巨牛的 人工智能学习网站&#xff0c; 通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一下给大家。 …...

深入了解Matplotlib中的子图创建方法

深入了解Matplotlib中的子图创建方法 一 add_axes( **kwargs):1.1 函数介绍1.2 示例一 创建第一张子图1.2 示例二 polar参数的运用1.3 示例三 创建多张子图 二 add_subplot(*args, **kwargs):2.1 函数介绍2.2 示例一 三 两种方法的区别3.1 参数形式3.2 布局灵活性3.3 适用场景3…...

云计算运维 · 第三阶段 · git

学习b记 第三阶段 三、持续集成 1、git #安装 yum -y install git[rootgit-git ~]# git config –-global user.name "qxl" # 配置git使用用户 [rootgit-git ~]# git config –-global user.email "qxlmail.com" # 配置git使用邮箱 [rootgit-git ~]# g…...

【幻兽帕鲁】开服务器,高性能高带宽(100mbps),免费!!!【学生党强推】

【幻兽帕鲁】开服务器&#xff0c;高性能高带宽&#xff08;100mbps&#xff09;&#xff0c;免费&#xff01;&#xff01;&#xff01;【学生党强推】 教程相关视频地址&#xff1a;https://www.bilibili.com/video/BV16e411Y7Fd/ 目前幻兽帕鲁开服务器有以下几套比较性价比的…...

微信小程序|推箱子小游戏

推箱子游戏是一种经典的益智游戏,通过移动箱子将其推到指定位置,完成关卡的过程。随着小程序的发展,越来越多的人开始在手机上玩推箱子游戏。本文将介绍如何利用小程序实现推箱子游戏,并分享一些技术实现的方法。 目录 引言游戏背景介绍游戏规则及挑战技术实现步骤创建游戏…...

【Linux】—— 信号的产生

本期&#xff0c;我们今天要将的是信号的第二个知识&#xff0c;即信号的产生。 目录 &#xff08;一&#xff09;通过终端按键产生信号 &#xff08;二&#xff09;调用系统函数向进程发信号 &#xff08;三&#xff09;由软件条件产生信号 &#xff08;四&#xff09;硬件…...

【算法】Hash 算法-关注优化细节

//给定一个未排序的整数数组 nums &#xff0c;找出数字连续的最长序列&#xff08;不要求序列元素在原数组中连续&#xff09;的长度。 // // 请你设计并实现时间复杂度为 O(n) 的算法解决此问题。 // // // // 示例 1&#xff1a; // // //输入&#xff1a;nums [100,4…...

回归预测 | Matlab实现CPO-SVR冠豪猪优化支持向量机的数据多输入单输出回归预测

回归预测 | Matlab实现CPO-SVR冠豪猪优化支持向量机的数据多输入单输出回归预测 目录 回归预测 | Matlab实现CPO-SVR冠豪猪优化支持向量机的数据多输入单输出回归预测预测效果基本描述程序设计参考资料 预测效果 基本描述 1.Matlab实现CPO-SVR冠豪猪优化支持向量机的数据多输入…...

Idea设置代理后无法clone git项目

背景 对于我们程序员来说&#xff0c;经常上github找项目、找资料是必不可少的&#xff0c;但是一些原因&#xff0c;我们访问的时候速度特别的慢&#xff0c;需要有个代理&#xff0c;才能正常的访问。 今天碰到个问题&#xff0c;使用idea工具 clone项目&#xff0c;速度特…...

基于算法竞赛的c++编程(28)结构体的进阶应用

结构体的嵌套与复杂数据组织 在C中&#xff0c;结构体可以嵌套使用&#xff0c;形成更复杂的数据结构。例如&#xff0c;可以通过嵌套结构体描述多层级数据关系&#xff1a; struct Address {string city;string street;int zipCode; };struct Employee {string name;int id;…...

深入剖析AI大模型:大模型时代的 Prompt 工程全解析

今天聊的内容&#xff0c;我认为是AI开发里面非常重要的内容。它在AI开发里无处不在&#xff0c;当你对 AI 助手说 "用李白的风格写一首关于人工智能的诗"&#xff0c;或者让翻译模型 "将这段合同翻译成商务日语" 时&#xff0c;输入的这句话就是 Prompt。…...

【HarmonyOS 5.0】DevEco Testing:鸿蒙应用质量保障的终极武器

——全方位测试解决方案与代码实战 一、工具定位与核心能力 DevEco Testing是HarmonyOS官方推出的​​一体化测试平台​​&#xff0c;覆盖应用全生命周期测试需求&#xff0c;主要提供五大核心能力&#xff1a; ​​测试类型​​​​检测目标​​​​关键指标​​功能体验基…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

C++ 基础特性深度解析

目录 引言 一、命名空间&#xff08;namespace&#xff09; C 中的命名空间​ 与 C 语言的对比​ 二、缺省参数​ C 中的缺省参数​ 与 C 语言的对比​ 三、引用&#xff08;reference&#xff09;​ C 中的引用​ 与 C 语言的对比​ 四、inline&#xff08;内联函数…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

关于 WASM:1. WASM 基础原理

一、WASM 简介 1.1 WebAssembly 是什么&#xff1f; WebAssembly&#xff08;WASM&#xff09; 是一种能在现代浏览器中高效运行的二进制指令格式&#xff0c;它不是传统的编程语言&#xff0c;而是一种 低级字节码格式&#xff0c;可由高级语言&#xff08;如 C、C、Rust&am…...

汇编常见指令

汇编常见指令 一、数据传送指令 指令功能示例说明MOV数据传送MOV EAX, 10将立即数 10 送入 EAXMOV [EBX], EAX将 EAX 值存入 EBX 指向的内存LEA加载有效地址LEA EAX, [EBX4]将 EBX4 的地址存入 EAX&#xff08;不访问内存&#xff09;XCHG交换数据XCHG EAX, EBX交换 EAX 和 EB…...