当前位置: 首页 > 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;速度特…...

从WWDC看苹果产品发展的规律

WWDC 是苹果公司一年一度面向全球开发者的盛会&#xff0c;其主题演讲展现了苹果在产品设计、技术路线、用户体验和生态系统构建上的核心理念与演进脉络。我们借助 ChatGPT Deep Research 工具&#xff0c;对过去十年 WWDC 主题演讲内容进行了系统化分析&#xff0c;形成了这份…...

Psychopy音频的使用

Psychopy音频的使用 本文主要解决以下问题&#xff1a; 指定音频引擎与设备&#xff1b;播放音频文件 本文所使用的环境&#xff1a; Python3.10 numpy2.2.6 psychopy2025.1.1 psychtoolbox3.0.19.14 一、音频配置 Psychopy文档链接为Sound - for audio playback — Psy…...

安卓基础(aar)

重新设置java21的环境&#xff0c;临时设置 $env:JAVA_HOME "D:\Android Studio\jbr" 查看当前环境变量 JAVA_HOME 的值 echo $env:JAVA_HOME 构建ARR文件 ./gradlew :private-lib:assembleRelease 目录是这样的&#xff1a; MyApp/ ├── app/ …...

MySQL JOIN 表过多的优化思路

当 MySQL 查询涉及大量表 JOIN 时&#xff0c;性能会显著下降。以下是优化思路和简易实现方法&#xff1a; 一、核心优化思路 减少 JOIN 数量 数据冗余&#xff1a;添加必要的冗余字段&#xff08;如订单表直接存储用户名&#xff09;合并表&#xff1a;将频繁关联的小表合并成…...

破解路内监管盲区:免布线低位视频桩重塑停车管理新标准

城市路内停车管理常因行道树遮挡、高位设备盲区等问题&#xff0c;导致车牌识别率低、逃费率高&#xff0c;传统模式在复杂路段束手无策。免布线低位视频桩凭借超低视角部署与智能算法&#xff0c;正成为破局关键。该设备安装于车位侧方0.5-0.7米高度&#xff0c;直接规避树枝遮…...

【堆垛策略】设计方法

堆垛策略的设计是积木堆叠系统的核心&#xff0c;直接影响堆叠的稳定性、效率和容错能力。以下是分层次的堆垛策略设计方法&#xff0c;涵盖基础规则、优化算法和容错机制&#xff1a; 1. 基础堆垛规则 (1) 物理稳定性优先 重心原则&#xff1a; 大尺寸/重量积木在下&#xf…...

【Kafka】Kafka从入门到实战:构建高吞吐量分布式消息系统

Kafka从入门到实战:构建高吞吐量分布式消息系统 一、Kafka概述 Apache Kafka是一个分布式流处理平台,最初由LinkedIn开发,后成为Apache顶级项目。它被设计用于高吞吐量、低延迟的消息处理,能够处理来自多个生产者的海量数据,并将这些数据实时传递给消费者。 Kafka核心特…...

解析“道作为序位生成器”的核心原理

解析“道作为序位生成器”的核心原理 以下完整展开道函数的零点调控机制&#xff0c;重点解析"道作为序位生成器"的核心原理与实现框架&#xff1a; 一、道函数的零点调控机制 1. 道作为序位生成器 道在认知坐标系$(x_{\text{物}}, y_{\text{意}}, z_{\text{文}}…...

TCP/IP 网络编程 | 服务端 客户端的封装

设计模式 文章目录 设计模式一、socket.h 接口&#xff08;interface&#xff09;二、socket.cpp 实现&#xff08;implementation&#xff09;三、server.cpp 使用封装&#xff08;main 函数&#xff09;四、client.cpp 使用封装&#xff08;main 函数&#xff09;五、退出方法…...

聚六亚甲基单胍盐酸盐市场深度解析:现状、挑战与机遇

根据 QYResearch 发布的市场报告显示&#xff0c;全球市场规模预计在 2031 年达到 9848 万美元&#xff0c;2025 - 2031 年期间年复合增长率&#xff08;CAGR&#xff09;为 3.7%。在竞争格局上&#xff0c;市场集中度较高&#xff0c;2024 年全球前十强厂商占据约 74.0% 的市场…...