5.排序算法之二:选择排序
选择排序(select sort)
在无序列表中,把无序列表分成有序区(刚开始有序区元素个数为0)和无序区(刚开始无序区元素个数为n),循环n-1趟,每一趟找到最小或最大的那个元素,并把最小或最大的那个元素放在有序区,此时有序区元素个数加1,无序区元素个数减1,直到循环n-1趟后,列表都已排序好,此时,有序区的元素个数为n,无序区元素个数为0。
代码关键点分析:
总趟数(n-1)
无序列表:arr[n] = {val0, val1, ..., val(n-1)};
n = 1时,即无序列表只有1个元素,只要进行比较0趟
n = 2 时,即无序列表有2个元素,只要进行比较1趟
n = 3 时,即无序列表有3个元素,只要进行比较2趟
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.排序算法之二:选择排序
选择排序(select sort)在无序列表中,把无序列表分成有序区(刚开始有序区元素个数为0)和无序区(刚开始无序区元素个数为n),循环n-1趟,每一趟找到最小或最大的那个元素&…...
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)
可信计算组织(Ttrusted Computing Group,TCG)是一个非盈利的工业标准组织,它的宗旨是加强在相异计算机平台上的计算环境的安全性。TCG于2003年春成立,并采纳了由可信计算平台联盟(the Trusted Computing Platform Alli…...
这篇教你搞定Android内存优化分析总结
一、内存优化概念1.1 为什么要做内存优化?内存优化一直是一个很重要但却缺乏关注的点,内存作为程序运行最重要的资源之一,需要运行过程中做到合理的资源分配与回收,不合理的内存占用轻则使得用户应用程序运行卡顿、ANR、黑屏&…...
概率论与数理统计期末小题狂练 11-12两套,12-13-1
11-12第一学期A1 略。2 X服从正态分布N(0,1),X^2服从卡方分布。又考查了卡方分布均值和方差公式。一开始如果对本题无从下手,大概是没看出来是什么分布。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.项目:创造唯一的产品,唯一的服务临时性的努力 2.项目特征:不可见性,复杂性,一致性,变更性,特殊性 3.项目和日常活动的区别? 项目具有特殊性,负责人是项目经理&#…...
云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 后, 拖动 bin 文件夹到控制台&…...
如何使用BeaconEye监控CobaltStrike的Beacon
关于BeaconEye BeaconEye是一款针对CobaltStrike的安全工具,该工具可以扫描正在运行的主动CobaltStrike Beacon。当BeaconEye扫描到了正在运行Beacon的进程之后,BeaconEye将会监控每一个进程以查看C2活动。 工作机制 BeaconEye将会扫描活动进程或Mini…...
STM32开发(17)----CubeMX配置CRC
CubeMX配置CRC前言一、什么是CRC?二、实验过程1.STM32CubeMX配置2.代码实现重载printf3.实验结果总结前言 本章介绍使用STM32CubeMX对CRC进行配置的方法,CRC的目的是保证数据的完整性,所有的STM32芯片都内置了一个硬件的CRC计算模块…...
【MySQL】基础操作:登录、访问、退出和卸载
一、MySQL简介 MySQL数据库最初是由瑞典MySQL AB公司开发,2008年1月16号被Sun公司收购。2009年,SUN又被Oracle收购。MySQL是目前IT行业最流行的开放源代码的数据库管理系统,同时它也是一个支持多线程、高并发、多用户的关系型数据库管理系统。…...
【算法经典题集】递推(持续更新~~~)
😽PREFACE🎁欢迎各位→点赞👍 收藏⭐ 评论📝📢系列专栏:算法经典题集🔊本专栏涉及到的知识点或者题目是算法专栏的补充与应用💪种一棵树最好是十年前其次是现在递推简单的斐波那契…...
mysql兼容性验证
MySQL是一个关系型数据库管理系统。 一、安装启动 安装mysql相关软件包 yum install mysql-server 启动mysql服务 systemctl start mysqld systemctl status mysqld mysql数据库启动失败问题汇总: <问题1>、start mysqld显示失败,如下所示&…...
C++回顾(五)—— 构造函数和析构函数
5.1 构造和析构 5.1.1 构造函数 (1)定义 1)C中的类可以定义与类名相同的特殊成员函数,这种与类名相同的成员函数叫做构造函数;2)构造函数在定义时可以有参数;3)没有任何返回类型的…...
嵌入式学习笔记——概述
嵌入式系统概述前言“嵌入式系统”概念1.是个啥?2.可以干啥?3.有哪些入坑方向?4.入坑后可以有多少薪资?单片机1.什么是单片机?2.架构简介3.基于ARM架构的单片机结构简介总结前言 断更很长时间了,写博客确实…...
化繁为简高效部署 华为云发布部署服务CodeArts Deploy
随着互联网、数字化的发展,公司机构与各类企业往往需要进行大量频繁的软件部署,部署设备类型多样,如:本地机器、云上裸金属服务器、云上虚拟机与容器等。面对多种部署模式、分布式复杂运行环境,如何用最短时间、高质…...
注意力机制详解系列(四):混合注意力机制
👨💻作者简介: 大数据专业硕士在读,CSDN人工智能领域博客专家,阿里云专家博主,专注大数据与人工智能知识分享。 🎉专栏推荐: 目前在写CV方向专栏,更新不限于目标检测、OCR、图像分类、图像分割等方向,目前活动仅19.9,虽然付费但会长期更新,感兴趣的小伙伴可以…...
Makefiles学习1
初识"Makefiles" 创建一个 “Makefile” 文件 touch Makefile“touch” 用于修改文件或者目录的时间属性,包括访问时间和修改时间,若文件不存在,则重新建立一个新的文件。这里有两个需要我们注意的: 进入并编辑"…...
python打卡day49
知识点回顾: 通道注意力模块复习空间注意力模块CBAM的定义 作业:尝试对今天的模型检查参数数目,并用tensorboard查看训练过程 import torch import torch.nn as nn# 定义通道注意力 class ChannelAttention(nn.Module):def __init__(self,…...
shell脚本--常见案例
1、自动备份文件或目录 2、批量重命名文件 3、查找并删除指定名称的文件: 4、批量删除文件 5、查找并替换文件内容 6、批量创建文件 7、创建文件夹并移动文件 8、在文件夹中查找文件...
将对透视变换后的图像使用Otsu进行阈值化,来分离黑色和白色像素。这句话中的Otsu是什么意思?
Otsu 是一种自动阈值化方法,用于将图像分割为前景和背景。它通过最小化图像的类内方差或等价地最大化类间方差来选择最佳阈值。这种方法特别适用于图像的二值化处理,能够自动确定一个阈值,将图像中的像素分为黑色和白色两类。 Otsu 方法的原…...
《通信之道——从微积分到 5G》读书总结
第1章 绪 论 1.1 这是一本什么样的书 通信技术,说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号(调制) 把信息从信号中抽取出来&am…...
如何将联系人从 iPhone 转移到 Android
从 iPhone 换到 Android 手机时,你可能需要保留重要的数据,例如通讯录。好在,将通讯录从 iPhone 转移到 Android 手机非常简单,你可以从本文中学习 6 种可靠的方法,确保随时保持连接,不错过任何信息。 第 1…...
QT: `long long` 类型转换为 `QString` 2025.6.5
在 Qt 中,将 long long 类型转换为 QString 可以通过以下两种常用方法实现: 方法 1:使用 QString::number() 直接调用 QString 的静态方法 number(),将数值转换为字符串: long long value 1234567890123456789LL; …...
【从零学习JVM|第三篇】类的生命周期(高频面试题)
前言: 在Java编程中,类的生命周期是指类从被加载到内存中开始,到被卸载出内存为止的整个过程。了解类的生命周期对于理解Java程序的运行机制以及性能优化非常重要。本文会深入探寻类的生命周期,让读者对此有深刻印象。 目录 …...
CRMEB 中 PHP 短信扩展开发:涵盖一号通、阿里云、腾讯云、创蓝
目前已有一号通短信、阿里云短信、腾讯云短信扩展 扩展入口文件 文件目录 crmeb\services\sms\Sms.php 默认驱动类型为:一号通 namespace crmeb\services\sms;use crmeb\basic\BaseManager; use crmeb\services\AccessTokenServeService; use crmeb\services\sms\…...
日常一水C
多态 言简意赅:就是一个对象面对同一事件时做出的不同反应 而之前的继承中说过,当子类和父类的函数名相同时,会隐藏父类的同名函数转而调用子类的同名函数,如果要调用父类的同名函数,那么就需要对父类进行引用&#…...
前端中slice和splic的区别
1. slice slice 用于从数组中提取一部分元素,返回一个新的数组。 特点: 不修改原数组:slice 不会改变原数组,而是返回一个新的数组。提取数组的部分:slice 会根据指定的开始索引和结束索引提取数组的一部分。不包含…...
