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

5.排序算法之二:选择排序

选择排序(select sort)

在无序列表中,把无序列表分成有序区(刚开始有序区元素个数为0)和无序区(刚开始无序区元素个数为n),循环n-1趟,每一趟找到最小或最大的那个元素,并把最小或最大的那个元素放在有序区,此时有序区元素个数加1,无序区元素个数减1,直到循环n-1趟后,列表都已排序好,此时,有序区的元素个数为n,无序区元素个数为0。

代码关键点分析:

总趟数(n-1)

无序列表:arr[n] = {val0, val1, ..., val(n-1)};

  1. n = 1时,即无序列表只有1个元素,只要进行比较0趟

  1. n = 2 时,即无序列表有2个元素,只要进行比较1趟

  1. n = 3 时,即无序列表有3个元素,只要进行比较2趟

  1. n = n 时,即无序列表有n个元素,只要进行比较 n - 1 趟

每一趟下标最大值为(n-1)

代码:

#include <iostream>using namespace std;template<typename T>
void select_sort(T *arr, int n)
{int min_key;T temp;for (int i = 0; i < n-1; i++) //总趟数n-1{min_key = i;    for (int j = i+1; j < n; j++) //每一趟下标的最大值为n-1{if (arr[j] < arr[min_key])min_key = j;}if (min_key != i){temp = arr[i];arr[i] = arr[min_key];arr[min_key] = temp;}}
}int main(int argc, char *argv[])
{int arr[] = {3,5,2,1,4};int n = sizeof(arr)/sizeof(*arr);cout << "---before select sort---" << endl;for (int i = 0; i < n; i++){cout << arr[i] << " ";}cout << endl;select_sort(arr, n);cout << "---after select sort---" << endl;for (int i = 0; i < n; i++){cout << arr[i] << " ";}cout << endl;return 0;
}

结果:

时间复杂度:O()

选择排序算法,外循环对总趟数进行循环,内循环对每一趟进行循环,所以,算法时间复杂度为:O()

算法稳定性:不稳定

选择排序算法是不稳定的排序算法,因为每次都是在未排序的元素列中,找到最小的那个元素,放到已排序的元素列的末尾,可能会调换两个相等元素的先后位置,那么原序列中两个相等元素的先后顺序就破坏了,所以选择排序算法是不稳定的排序算法。比如{3,3,1,2},第一趟排序中,首位置的3和第3个位置的1进行互换,得到的{1,3,3,2},最开始的首位置的3和第2位置的3的先后位置就破坏了。

相关文章:

5.排序算法之二:选择排序

选择排序&#xff08;select sort&#xff09;在无序列表中&#xff0c;把无序列表分成有序区&#xff08;刚开始有序区元素个数为0&#xff09;和无序区&#xff08;刚开始无序区元素个数为n&#xff09;&#xff0c;循环n-1趟&#xff0c;每一趟找到最小或最大的那个元素&…...

Ubuntu18系统安装:node及node版本管理工具nvm部署前端项目

注意在安装之前先安装好Git 如何在Ubuntu 上安装Git与入门教程_ubuntu安装git_飞鹰雪菲的博客-CSDN博客 1、把nvm远程镜像克隆到指定目录 git clone https://gitee.com/mirrors/nvm 1.1在终端指定的文件夹下 drciZwz91oq31508figapkas0Z:~/qiang/tools$ git clone https://…...

统计学 假设检验

文章目录假设检验假设检验的基本原理提出假设作出决策表述决策结果一个总体参数的检验总体均值的检验总体比例的检验总体方差的检验两个总体参数的检验两个总体均值之差的检验两个总体比例之差的检验两个总体方差比的检验总体分布的检验正态性检验的图示法Shapiro-Wilk 和 K-S …...

【C++】哈希

哈希一、unordered系列关联式容器二、哈希原理2.1 哈希映射2.2 哈希冲突2.2.1 闭散列—开放地址法2.2.2 代码实现2.2.3 开散列—拉链法2.2.4 代码实现三、哈希封装unordered_map/unordered_set3.1 基本框架3.2 迭代器实现3.2.3 operator*和operator->和operator!3.2.4 opera…...

「TCG 规范解读」PC 平台相关规范(3)

可信计算组织&#xff08;Ttrusted Computing Group,TCG&#xff09;是一个非盈利的工业标准组织&#xff0c;它的宗旨是加强在相异计算机平台上的计算环境的安全性。TCG于2003年春成立&#xff0c;并采纳了由可信计算平台联盟&#xff08;the Trusted Computing Platform Alli…...

这篇教你搞定Android内存优化分析总结

一、内存优化概念1.1 为什么要做内存优化&#xff1f;内存优化一直是一个很重要但却缺乏关注的点&#xff0c;内存作为程序运行最重要的资源之一&#xff0c;需要运行过程中做到合理的资源分配与回收&#xff0c;不合理的内存占用轻则使得用户应用程序运行卡顿、ANR、黑屏&…...

概率论与数理统计期末小题狂练 11-12两套,12-13-1

11-12第一学期A1 略。2 X服从正态分布N&#xff08;0&#xff0c;1&#xff09;&#xff0c;X^2服从卡方分布。又考查了卡方分布均值和方差公式。一开始如果对本题无从下手&#xff0c;大概是没看出来是什么分布。3 第二小空本身也可以作为一个结论。4 考查切比雪夫不等式&…...

golang对字符串的处理操作 如何正确理解 rune byte和string

fmt.Printf相关参数介绍 先来看代码的演示 package mainimport ("fmt""unicode/utf8" )func main() {s:"我爱中国人haha!"fmt.Println(len(s))//20个字节 一个中文三个字节 1541fmt.Print("\n echo byte \n")for k,v: range []byte(…...

软件项目管理简答题复习(1)

1.项目&#xff1a;创造唯一的产品&#xff0c;唯一的服务临时性的努力 2.项目特征&#xff1a;不可见性&#xff0c;复杂性&#xff0c;一致性&#xff0c;变更性&#xff0c;特殊性 3.项目和日常活动的区别&#xff1f; 项目具有特殊性&#xff0c;负责人是项目经理&#…...

云Windows Server 2022 Datacenter 安装MySQL8解压缩版 mysql-8.0.32-winx64 230301记录

MySQL Community Downloads MySQL社区版压缩包下载地址 https://dev.mysql.com/downloads/mysql/ 解压到了C盘 没打算设置环境变量 右键点击开始 或 winx 以管理员身份打开 PowerShell 进入到安装目录下的 bin 目录 可以输入cd 后&#xff0c; 拖动 bin 文件夹到控制台&…...

如何使用BeaconEye监控CobaltStrike的Beacon

关于BeaconEye BeaconEye是一款针对CobaltStrike的安全工具&#xff0c;该工具可以扫描正在运行的主动CobaltStrike Beacon。当BeaconEye扫描到了正在运行Beacon的进程之后&#xff0c;BeaconEye将会监控每一个进程以查看C2活动。 工作机制 BeaconEye将会扫描活动进程或Mini…...

STM32开发(17)----CubeMX配置CRC

CubeMX配置CRC前言一、什么是CRC&#xff1f;二、实验过程1.STM32CubeMX配置2.代码实现重载printf3.实验结果总结前言 本章介绍使用STM32CubeMX对CRC进行配置的方法&#xff0c;CRC的目的是保证数据的完整性&#xff0c;所有的STM32芯片都内置了一个硬件的CRC计算模块&#xf…...

【MySQL】基础操作:登录、访问、退出和卸载

一、MySQL简介 MySQL数据库最初是由瑞典MySQL AB公司开发&#xff0c;2008年1月16号被Sun公司收购。2009年&#xff0c;SUN又被Oracle收购。MySQL是目前IT行业最流行的开放源代码的数据库管理系统&#xff0c;同时它也是一个支持多线程、高并发、多用户的关系型数据库管理系统。…...

【算法经典题集】递推(持续更新~~~)

&#x1f63d;PREFACE&#x1f381;欢迎各位→点赞&#x1f44d; 收藏⭐ 评论&#x1f4dd;&#x1f4e2;系列专栏&#xff1a;算法经典题集&#x1f50a;本专栏涉及到的知识点或者题目是算法专栏的补充与应用&#x1f4aa;种一棵树最好是十年前其次是现在递推简单的斐波那契…...

mysql兼容性验证

MySQL是一个关系型数据库管理系统。 一、安装启动 安装mysql相关软件包 yum install mysql-server 启动mysql服务 systemctl start mysqld systemctl status mysqld mysql数据库启动失败问题汇总&#xff1a; <问题1>、start mysqld显示失败&#xff0c;如下所示&…...

C++回顾(五)—— 构造函数和析构函数

5.1 构造和析构 5.1.1 构造函数 &#xff08;1&#xff09;定义 1&#xff09;C中的类可以定义与类名相同的特殊成员函数&#xff0c;这种与类名相同的成员函数叫做构造函数&#xff1b;2&#xff09;构造函数在定义时可以有参数&#xff1b;3&#xff09;没有任何返回类型的…...

嵌入式学习笔记——概述

嵌入式系统概述前言“嵌入式系统”概念1.是个啥&#xff1f;2.可以干啥&#xff1f;3.有哪些入坑方向&#xff1f;4.入坑后可以有多少薪资&#xff1f;单片机1.什么是单片机&#xff1f;2.架构简介3.基于ARM架构的单片机结构简介总结前言 断更很长时间了&#xff0c;写博客确实…...

化繁为简高效部署 华为云发布部署服务CodeArts Deploy

​随着互联网、数字化的发展&#xff0c;公司机构与各类企业往往需要进行大量频繁的软件部署&#xff0c;部署设备类型多样&#xff0c;如&#xff1a;本地机器、云上裸金属服务器、云上虚拟机与容器等。面对多种部署模式、分布式复杂运行环境&#xff0c;如何用最短时间、高质…...

注意力机制详解系列(四):混合注意力机制

👨‍💻作者简介: 大数据专业硕士在读,CSDN人工智能领域博客专家,阿里云专家博主,专注大数据与人工智能知识分享。 🎉专栏推荐: 目前在写CV方向专栏,更新不限于目标检测、OCR、图像分类、图像分割等方向,目前活动仅19.9,虽然付费但会长期更新,感兴趣的小伙伴可以…...

Makefiles学习1

初识"Makefiles" 创建一个 “Makefile” 文件 touch Makefile“touch” 用于修改文件或者目录的时间属性&#xff0c;包括访问时间和修改时间&#xff0c;若文件不存在&#xff0c;则重新建立一个新的文件。这里有两个需要我们注意的&#xff1a; 进入并编辑"…...

C++实现分布式网络通信框架RPC(3)--rpc调用端

目录 一、前言 二、UserServiceRpc_Stub 三、 CallMethod方法的重写 头文件 实现 四、rpc调用端的调用 实现 五、 google::protobuf::RpcController *controller 头文件 实现 六、总结 一、前言 在前边的文章中&#xff0c;我们已经大致实现了rpc服务端的各项功能代…...

蓝牙 BLE 扫描面试题大全(2):进阶面试题与实战演练

前文覆盖了 BLE 扫描的基础概念与经典问题蓝牙 BLE 扫描面试题大全(1)&#xff1a;从基础到实战的深度解析-CSDN博客&#xff0c;但实际面试中&#xff0c;企业更关注候选人对复杂场景的应对能力&#xff08;如多设备并发扫描、低功耗与高发现率的平衡&#xff09;和前沿技术的…...

高危文件识别的常用算法:原理、应用与企业场景

高危文件识别的常用算法&#xff1a;原理、应用与企业场景 高危文件识别旨在检测可能导致安全威胁的文件&#xff0c;如包含恶意代码、敏感数据或欺诈内容的文档&#xff0c;在企业协同办公环境中&#xff08;如Teams、Google Workspace&#xff09;尤为重要。结合大模型技术&…...

【Zephyr 系列 10】实战项目:打造一个蓝牙传感器终端 + 网关系统(完整架构与全栈实现)

🧠关键词:Zephyr、BLE、终端、网关、广播、连接、传感器、数据采集、低功耗、系统集成 📌目标读者:希望基于 Zephyr 构建 BLE 系统架构、实现终端与网关协作、具备产品交付能力的开发者 📊篇幅字数:约 5200 字 ✨ 项目总览 在物联网实际项目中,**“终端 + 网关”**是…...

GitHub 趋势日报 (2025年06月08日)

&#x1f4ca; 由 TrendForge 系统生成 | &#x1f310; https://trendforge.devlive.org/ &#x1f310; 本日报中的项目描述已自动翻译为中文 &#x1f4c8; 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...

select、poll、epoll 与 Reactor 模式

在高并发网络编程领域&#xff0c;高效处理大量连接和 I/O 事件是系统性能的关键。select、poll、epoll 作为 I/O 多路复用技术的代表&#xff0c;以及基于它们实现的 Reactor 模式&#xff0c;为开发者提供了强大的工具。本文将深入探讨这些技术的底层原理、优缺点。​ 一、I…...

在WSL2的Ubuntu镜像中安装Docker

Docker官网链接: https://docs.docker.com/engine/install/ubuntu/ 1、运行以下命令卸载所有冲突的软件包&#xff1a; for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done2、设置Docker…...

全志A40i android7.1 调试信息打印串口由uart0改为uart3

一&#xff0c;概述 1. 目的 将调试信息打印串口由uart0改为uart3。 2. 版本信息 Uboot版本&#xff1a;2014.07&#xff1b; Kernel版本&#xff1a;Linux-3.10&#xff1b; 二&#xff0c;Uboot 1. sys_config.fex改动 使能uart3(TX:PH00 RX:PH01)&#xff0c;并让boo…...

分布式增量爬虫实现方案

之前我们在讨论的是分布式爬虫如何实现增量爬取。增量爬虫的目标是只爬取新产生或发生变化的页面&#xff0c;避免重复抓取&#xff0c;以节省资源和时间。 在分布式环境下&#xff0c;增量爬虫的实现需要考虑多个爬虫节点之间的协调和去重。 另一种思路&#xff1a;将增量判…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...