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

手撕排序之直接选择排序

前言:

直接选择排序是排序中比较简单的排序,同时也是时间复杂度不是很优的排序。

思想:

本文主要讲解直接选择排序的优化版本。

我们经过一次遍历直接将该数列中最大的和最小的值挑选出来,如果是升序,就将最小的和首元素进行交换,最大的与尾元素进行交换。然后将首部元素++,尾部元素--,重新遍历再次选择次大的和次小的。以此类推。

注意:

按照上面的思路会遇到一些特殊情况,造成排序的失败。

比如说我们先将最大的值赋给尾部元素,如果最大的值正好在头部元素,而最小的值恰好在尾部元素,这样就导致把最大的元素赋给尾部元素时,会把尾部本来的最小值覆盖掉,造成排序的失败。

为了解决这种情况,我们只需要将尾部元素提前存储好就欧克拉~

原码:

void SelectSort(int* a, int n)
{int begin = 0;int end = n - 1;while (begin <= end){int maxi = begin, mini = begin;for (int i = begin + 1; i < end + 1; i++){//找出最大值和最小值的下标if (a[i] > a[maxi])maxi = i;if (a[i] < a[mini])mini = i;}Swap(&a[begin], &a[mini]);//max如果被换走,就修正以下if (maxi == begin)maxi = mini;Swap(&a[end], &a[maxi]);begin++;end--;}
}

时间复杂度:
n + n-2 + n - 4 + n - 6……

这也是一个等差数列,所以时间复杂度就是O(N^2)。

显然这并不是一个优的排序算法。

相关文章:

手撕排序之直接选择排序

前言&#xff1a; 直接选择排序是排序中比较简单的排序&#xff0c;同时也是时间复杂度不是很优的排序。 思想&#xff1a; 本文主要讲解直接选择排序的优化版本。 我们经过一次遍历直接将该数列中最大的和最小的值挑选出来&#xff0c;如果是升序&#xff0c;就将最小的和…...

洛谷 P1359 租用游艇

题目链接 P1359 租用游艇 普及 题目描述 长江游艇俱乐部在长江上设置了 n n n 个游艇出租站 1 , 2 , 3 , . . . , n 1,2,3,...,n 1,2,3,...,n&#xff0c;游客可在这些游艇出租站租用游艇&#xff0c;并在下游的任何一个游艇出租站归还游艇。游艇出租站 i i i 到游艇出租站…...

springboot中没有主清单属性解决办法

在执行一个 spring boot 启动类时&#xff0c;提示 没有主清单属性 一般这个问题是没加 spring-boot-maven-plugin 插件的问题&#xff0c;但是项目中已经加了 <build><plugins><plugin><groupId>org.springframework.boot</groupId><artifa…...

C/C++ static关键字详解(最全解析,static是什么,static如何使用,static的常考面试题)

目录 一、前言 二、static关键字是什么&#xff1f; 三、static关键字修饰的对象是什么&#xff1f; 四、C 语言中的 static &#x1f34e;static的C用法 &#x1f349;static的重点概念 &#x1f350;static修饰局部变量 &#x1f4a6;static在修饰局部变量和函数的作用 &a…...

windwos10搭建我的世界服务器,并通过内网穿透实现联机游戏Minecraft

文章目录 1. Java环境搭建2.安装我的世界Minecraft服务3. 启动我的世界服务4.局域网测试连接我的世界服务器5. 安装cpolar内网穿透6. 创建隧道映射内网端口7. 测试公网远程联机8. 配置固定TCP端口地址8.1 保留一个固定tcp地址8.2 配置固定tcp地址 9. 使用固定公网地址远程联机 …...

【实战Flask API项目指南】之七 用JWT进行用户认证与授权

实战Flask API项目指南之 用JWT进行用户认证与授权 本系列文章将带你深入探索实战Flask API项目指南&#xff0c;通过跟随小菜的学习之旅&#xff0c;你将逐步掌握 Flask 在实际项目中的应用。让我们一起踏上这个精彩的学习之旅吧&#xff01; 前言 当小菜踏入Flask后端开发…...

鸿蒙LiteOs读源码教程+向LiteOS中添加一个简单的基于线程运行时的短作业优先调度策略

【⭐据说点赞收藏的都会收获好运哦&#x1f44d;】 一、鸿蒙Liteos读源码教程 鸿蒙的源码是放在openharmony文件夹下&#xff0c;openharmony下的kernel文件夹存放操作系统内核的相关代码和实现。 内核是操作系统的核心部分&#xff0c;所以像负责&#xff1a;资源管理、任…...

axios的使用与封装详细教程

目录 一、axios使用方式二、axios在main.js配置 一、axios使用方式 在 Spring Boot Vue 的项目中使用 Axios&#xff0c;你需要在 Vue 项目中安装 Axios 库&#xff0c;因为 Axios 是一个前端 JavaScript 库&#xff0c;用于发送 HTTP 请求和处理响应数据&#xff0c;而与 Sp…...

C++二叉搜索树

本章主要是二叉树的进阶部分&#xff0c;学习搜索二叉树可以更好理解后面的map和set的特性。 1.二叉搜索树概念 二叉搜索树的递归定义为&#xff1a;非空左子树所有元素都小于根节点的值&#xff0c;非空右子树所有元素都大于根节点的值&#xff0c;而左右子树也是二叉搜索树…...

elasticsearch索引按日期拆分

1.索引拆分原因 如果单个索引数据量过大会导致搜索变慢&#xff0c;而且不方便清理历史数据。 例如日志数据每天量很大&#xff0c;而且需要定期清理以往日志数据。例如原索引为sc_all_system_log&#xff0c;现按天拆分索引sc_all_system_log20220902&#xff0c;sc_all_syste…...

纯python实现大漠图色功能

大漠图色是一种自动化测试工具&#xff0c;可以用于识别屏幕上的图像并执行相应的操作。在Python中&#xff0c;可以使用第三方库pyautogui来实现大漠图色功能。具体步骤如下&#xff1a; 安装pyautogui库&#xff1a;在命令行中输入pip install pyautogui。导入pyautogui库&a…...

debounce and throtlle

debounce // 核心&#xff1a;单位时间内触发>1 则只执行最后一次。//excutioner 可以认为是执行器。执行器存在则清空&#xff0c;再赋值新的执行器。function debounce(fn, delay 500) {let excutioner null;return function () {let context this;let args arguments…...

四、数据库系统

数据库系统&#xff08;Database System&#xff09;&#xff0c;是由数据库及其管理软件组成的系统。数据库系统是为适应数据处理的需要而发展起来的一种较为理想的数据处理系统&#xff0c;也是一个为实际可运行的存储、维护和应用系统提供数据的软件系统&#xff0c;是存储介…...

Linux中的高级IO

文章目录 1.IO1.1基本介绍1.2基础io的低效性1.3如何提高IO效率1.4五种IO模型1.5非阻塞模式的设置 2.IO多路转接之Select2.1函数的基本了解2.2fd_set理解2.3完整例子代码&#xff08;会在代码中进行讲解&#xff09;2.4优缺点 3.多路转接之poll3.1poll函数的介绍3.2poll服务器3.…...

项目管理之如何估算项目工作成本

在项目管理中&#xff0c;如何估算项目工作成本是一个关键问题。为了解决这个问题&#xff0c;我们可以采用自上而下的成本限额估算法和自下而上的成本汇总估算法。这两种方法各有优缺点&#xff0c;但都可以帮助我们准确地估算项目工作成本。 自上而下的成本限额估算法 自上…...

Redis主从复制基础概念

Redis主从复制&#xff1a;提高数据可用性和性能的策略 一、概述 Redis主从复制是一种常用的高可用性策略&#xff0c;通过将数据从一个Redis服务器复制到另一个或多个Redis服务器上&#xff0c;以提高数据的可用性和读取性能。当主服务器出现故障时&#xff0c;可以快速地切…...

图数据库Neo4j概念、应用场景、安装及CQL的使用

一、图数据库概念 引用Seth Godin的说法&#xff0c;企业需要摒弃仅仅收集数据点的做法&#xff0c;开始着手建立数据之间的关联关系。数据点之间的关系甚至比单个点本身更为重要。 传统的**关系数据库管理系统(RDBMS)**并不擅长处理数据之间的关系&#xff0c;那些表状数据模…...

路由器基础(四): RIP原理与配置

路由信息协议 (Routing Information Protocol,RIP) 是最早使用的距离矢量路由协议。因为路由是以矢量(距离、方向)的方式被通告出去的&#xff0c;这里的距离是根据度量来决定的&#xff0c;所以叫“距离矢量”。 距离矢量路由算法是动态路由算法。它的工作流程是&#xff1a;…...

红外遥控开发RK3568-PWM-IR

提示:文章写完后,目录可以自动生成,如何生成可参考右边的帮助文档 文章目录 前言1.红外遥控的发送接收工作原理2.红外协议3.红外遥控系统框图4.遥控器添加方法4.1 记录键值4.2 添加键值总结前言 提示:这里可以添加本文要记录的大概内容: 1.红外遥控的发送接收工作原理 …...

go-sync-mutex

Sync ​ Go 语言作为一个原生支持用户态进程&#xff08;Goroutine&#xff09;的语言&#xff0c;当提到并发编程、多线程编程时&#xff0c;往往都离不开锁这一概念。锁是一种并发编程中的同步原语&#xff08;Synchronization Primitives&#xff09;&#xff0c;它能保证多…...

Cursor实现用excel数据填充word模版的方法

cursor主页&#xff1a;https://www.cursor.com/ 任务目标&#xff1a;把excel格式的数据里的单元格&#xff0c;按照某一个固定模版填充到word中 文章目录 注意事项逐步生成程序1. 确定格式2. 调试程序 注意事项 直接给一个excel文件和最终呈现的word文件的示例&#xff0c;…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

centos 7 部署awstats 网站访问检测

一、基础环境准备&#xff08;两种安装方式都要做&#xff09; bash # 安装必要依赖 yum install -y httpd perl mod_perl perl-Time-HiRes perl-DateTime systemctl enable httpd # 设置 Apache 开机自启 systemctl start httpd # 启动 Apache二、安装 AWStats&#xff0…...

鸿蒙DevEco Studio HarmonyOS 5跑酷小游戏实现指南

1. 项目概述 本跑酷小游戏基于鸿蒙HarmonyOS 5开发&#xff0c;使用DevEco Studio作为开发工具&#xff0c;采用Java语言实现&#xff0c;包含角色控制、障碍物生成和分数计算系统。 2. 项目结构 /src/main/java/com/example/runner/├── MainAbilitySlice.java // 主界…...

2023赣州旅游投资集团

单选题 1.“不登高山&#xff0c;不知天之高也&#xff1b;不临深溪&#xff0c;不知地之厚也。”这句话说明_____。 A、人的意识具有创造性 B、人的认识是独立于实践之外的 C、实践在认识过程中具有决定作用 D、人的一切知识都是从直接经验中获得的 参考答案: C 本题解…...

在web-view 加载的本地及远程HTML中调用uniapp的API及网页和vue页面是如何通讯的?

uni-app 中 Web-view 与 Vue 页面的通讯机制详解 一、Web-view 简介 Web-view 是 uni-app 提供的一个重要组件&#xff0c;用于在原生应用中加载 HTML 页面&#xff1a; 支持加载本地 HTML 文件支持加载远程 HTML 页面实现 Web 与原生的双向通讯可用于嵌入第三方网页或 H5 应…...

技术栈RabbitMq的介绍和使用

目录 1. 什么是消息队列&#xff1f;2. 消息队列的优点3. RabbitMQ 消息队列概述4. RabbitMQ 安装5. Exchange 四种类型5.1 direct 精准匹配5.2 fanout 广播5.3 topic 正则匹配 6. RabbitMQ 队列模式6.1 简单队列模式6.2 工作队列模式6.3 发布/订阅模式6.4 路由模式6.5 主题模式…...

C#中的CLR属性、依赖属性与附加属性

CLR属性的主要特征 封装性&#xff1a; 隐藏字段的实现细节 提供对字段的受控访问 访问控制&#xff1a; 可单独设置get/set访问器的可见性 可创建只读或只写属性 计算属性&#xff1a; 可以在getter中执行计算逻辑 不需要直接对应一个字段 验证逻辑&#xff1a; 可以…...

免费PDF转图片工具

免费PDF转图片工具 一款简单易用的PDF转图片工具&#xff0c;可以将PDF文件快速转换为高质量PNG图片。无需安装复杂的软件&#xff0c;也不需要在线上传文件&#xff0c;保护您的隐私。 工具截图 主要特点 &#x1f680; 快速转换&#xff1a;本地转换&#xff0c;无需等待上…...

人工智能--安全大模型训练计划:基于Fine-tuning + LLM Agent

安全大模型训练计划&#xff1a;基于Fine-tuning LLM Agent 1. 构建高质量安全数据集 目标&#xff1a;为安全大模型创建高质量、去偏、符合伦理的训练数据集&#xff0c;涵盖安全相关任务&#xff08;如有害内容检测、隐私保护、道德推理等&#xff09;。 1.1 数据收集 描…...