当前位置: 首页 > 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; 进入并编辑"…...

多云管理“拦路虎”:深入解析网络互联、身份同步与成本可视化的技术复杂度​

一、引言&#xff1a;多云环境的技术复杂性本质​​ 企业采用多云策略已从技术选型升维至生存刚需。当业务系统分散部署在多个云平台时&#xff0c;​​基础设施的技术债呈现指数级积累​​。网络连接、身份认证、成本管理这三大核心挑战相互嵌套&#xff1a;跨云网络构建数据…...

业务系统对接大模型的基础方案:架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

遍历 Map 类型集合的方法汇总

1 方法一 先用方法 keySet() 获取集合中的所有键。再通过 gey(key) 方法用对应键获取值 import java.util.HashMap; import java.util.Set;public class Test {public static void main(String[] args) {HashMap hashMap new HashMap();hashMap.put("语文",99);has…...

关于iview组件中使用 table , 绑定序号分页后序号从1开始的解决方案

问题描述&#xff1a;iview使用table 中type: "index",分页之后 &#xff0c;索引还是从1开始&#xff0c;试过绑定后台返回数据的id, 这种方法可行&#xff0c;就是后台返回数据的每个页面id都不完全是按照从1开始的升序&#xff0c;因此百度了下&#xff0c;找到了…...

【第二十一章 SDIO接口(SDIO)】

第二十一章 SDIO接口 目录 第二十一章 SDIO接口(SDIO) 1 SDIO 主要功能 2 SDIO 总线拓扑 3 SDIO 功能描述 3.1 SDIO 适配器 3.2 SDIOAHB 接口 4 卡功能描述 4.1 卡识别模式 4.2 卡复位 4.3 操作电压范围确认 4.4 卡识别过程 4.5 写数据块 4.6 读数据块 4.7 数据流…...

1.3 VSCode安装与环境配置

进入网址Visual Studio Code - Code Editing. Redefined下载.deb文件&#xff0c;然后打开终端&#xff0c;进入下载文件夹&#xff0c;键入命令 sudo dpkg -i code_1.100.3-1748872405_amd64.deb 在终端键入命令code即启动vscode 需要安装插件列表 1.Chinese简化 2.ros …...

MySQL账号权限管理指南:安全创建账户与精细授权技巧

在MySQL数据库管理中&#xff0c;合理创建用户账号并分配精确权限是保障数据安全的核心环节。直接使用root账号进行所有操作不仅危险且难以审计操作行为。今天我们来全面解析MySQL账号创建与权限分配的专业方法。 一、为何需要创建独立账号&#xff1f; 最小权限原则&#xf…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...

CVPR2025重磅突破:AnomalyAny框架实现单样本生成逼真异常数据,破解视觉检测瓶颈!

本文介绍了一种名为AnomalyAny的创新框架&#xff0c;该方法利用Stable Diffusion的强大生成能力&#xff0c;仅需单个正常样本和文本描述&#xff0c;即可生成逼真且多样化的异常样本&#xff0c;有效解决了视觉异常检测中异常样本稀缺的难题&#xff0c;为工业质检、医疗影像…...

Python训练营-Day26-函数专题1:函数定义与参数

题目1&#xff1a;计算圆的面积 任务&#xff1a; 编写一个名为 calculate_circle_area 的函数&#xff0c;该函数接收圆的半径 radius 作为参数&#xff0c;并返回圆的面积。圆的面积 π * radius (可以使用 math.pi 作为 π 的值)要求&#xff1a;函数接收一个位置参数 radi…...