【学习分享】小白写算法之选择排序篇

【学习分享】小白写算法之选择排序篇

  • 前言
  • 一、什么是选择排序算法
  • 二、选择排序算法如何实现
  • 三、C语言实现算法
  • 四、复杂度计算
  • 五、算法稳定性
  • 六、小结


前言

简单排序有三种,冒泡排序,插入排序和选择排序。这三种排序的算法算是入门级别的,打好基础再学习更深入的算法。
前两篇文章介绍了冒泡排序和插入排序,本篇学习选择排序。
【学习分享】小白写算法之冒泡排序篇
【学习分享】小白写算法之插入排序篇


一、什么是选择排序算法

选择排序,顾名思义就是每次执行都选择一个最小(或者最大)的数,然后组成一个有序序列。
在这里插入图片描述
如下动图演示了选择排序算法的运行过程,比较直观。
在这里插入图片描述


二、选择排序算法如何实现

我们以数组{6,5,3,2,6,1}为例,每一轮所要做的事就是取出无序序列中的最小值,然后和第i轮的值进行互换,然后循环直到成为有序序列
在这里插入图片描述

每一轮怎么找出最小值呢?以第2轮找2为例。
在这里插入图片描述
总结一下规律:
1、在第i轮需要实现将第i个数和最小数进行互换。
2、查找最小数,需要从j=i+1开始找到最后一个数。
互换的算法我们已经接触很多次了。那么实现起来就比较简单了。


三、C语言实现算法

void selectsort(int arr[],int n)   //选择排序算法
{
    int i,j,min_idx,temp;
    for(i=0;i<n-1;i++)
        {
            min_idx=i;             //标记最小值为第min_idx位,先设定为第i位为最小值。
            for(j=i+1;j<n;j++)      //从i+1开始遍历查找最小值。
		        {
                if(arr[j]<arr[min_idx])
                        min_idx = j;
		        }
            if(i!=min_idx)             //如果i不是最小位,那么第i位和第min_idx位进行互
                {
                    temp = arr[i];
                    arr[i] = arr[min_idx];
                    arr[min_idx] = temp;
                }
        }
}

加入打印后用gcc编译,结果符合预期。
在这里插入图片描述


四、复杂度计算

时间复杂度
跟冒泡排序和插入排序相似,时间复杂度嵌套了两次n,所以选择排序算法时间复杂度是O(n^2).
在这里插入图片描述

空间复杂度计算
四个临时变量i,j,min_idx,temp,所以只需要一个元素的辅助空间即可,空间复杂度为O(1)
在这里插入图片描述


五、算法稳定性

算法稳定性要看相同元素是否会互换,从例子中可以看到,最小值互换后,两个6的相对位置已经发生改变。
在这里插入图片描述
所以选择排序是不稳定的。


六、小结

简单算法对于入门来说是很好的学习方法,只要掌握要领,算法也能变得简单易懂~~

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/521563.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

UART设计

一、UART通信简介 通用异步收发器&#xff0c; 特点&#xff1a;串行、异步、全双工通信 优点&#xff1a;通信线路简单&#xff0c;传输距离远 缺点&#xff1a;传输速度慢 数据传输速率&#xff1a;波特率&#xff08;单位&#xff1a;baud&#xff0c;波特&#xff09; …

解决IDEA下载mysql驱动太慢

下载驱动 下载页 解压后&#xff0c;提取**.jar**文件&#xff0c;放到一个目录下(你自己决定这个目录) 打开IDEA项目&#xff0c;点击右侧的数据库选项卡 在打开的页面&#xff0c;点击号 依次选择&#xff1a;数据源->MySQL 在弹出的页面&#xff0c;依次选择&#…

注解式 WebSocket - 构建 群聊、单聊 系统

目录 前言 注解式 WebSocket 构建聊天系统 群聊系统&#xff08;基本框架&#xff09; 群聊系统&#xff08;添加昵称&#xff09; 单聊系统 WebSocket 作用域下无法注入 Spring Bean 对象&#xff1f; 考虑离线消息 前言 很久之前&#xff0c;咱们聊过 WebSocket 编程式…

华为ensp中高级acl (控制列表) 原理和配置命令 (详解)

作者主页&#xff1a;点击&#xff01; ENSP专栏&#xff1a;点击&#xff01; 创作时间&#xff1a;2024年4月6日23点18分 高级acl&#xff08;Access Control List&#xff09;是一种访问控制列表&#xff0c;可以根据数据包的源IP地址、目标IP地址、源端口、目标端口、协议…

【ARM 嵌入式 C 常用数据结构系列 25.1 -- linux 双向链表 list_head 使用详细介绍】

请阅读【嵌入式开发学习必备专栏 】 文章目录 内核双向链表双向链表的数据结构初始化双向链表在双向链表中添加元素遍历双向链表链表使用示例注意事项 内核双向链表 在Linux内核中&#xff0c;双向链表是一种广泛使用的数据结构&#xff0c;允许从任意节点高效地进行前向或后向…

STM32F407-SRAM

SRAM—> 内存 Flash–>硬盘 外置SRAM 可以存储1M数据 地址线&#xff1a;A0-A18&#xff1b;2^18次方&#xff1b;512K个数据块 每个数据块是2字节&#xff1b; 数据线&#xff1a;D0-D15 UB/LB 掩码&#xff1b;低电平有效 UB -》低电平-》数据高字节有效 LB-》低电平…

golang 选择排序

学习笔记&#xff5e; // Author sunwenbo // 2024/4/6 21:49 package mainimport "fmt"/* 选择排序基本介绍选择式排序也属于内部排序法&#xff0c;是从预排序的数据中按指定的规则选出某一元素&#xff0c;经过和其他元素重整&#xff0c;再依原则交换位置后达到…

轻量的 WebHook 工具:歪脖虎克

本篇文章聊聊轻量的网络钩子&#xff08;WebHook&#xff09;工具&#xff1a;歪脖虎克。 写在前面 这是一篇迟到很久的文章&#xff0c;在 21 年和 22 年的时候&#xff0c;我分享过两篇关于轻量的计划任务工具 Cronicle 的文章&#xff1a;《轻量的定时任务工具 Cronicle&a…

Linux(Ubuntu)中创建【samba】服务,用于和Windows系统之间共享文件

目录 1.先介绍一下什么是Samba 2.安装&#xff0c;配置服务 安装 配置&#xff08;smb.conf&#xff09; 配置用户 3.出现的问题&#xff08;Failed to add entry for user XXXX&#xff09; 4.创建文件夹 5.windows访问 1.先介绍一下什么是Samba Samba是一个开源的软…

2024.4.3-[作业记录]-day08-CSS 盒子模型(溢出显示、伪元素)

个人主页&#xff1a;学习前端的小z 个人专栏&#xff1a;HTML5和CSS3悦读 本专栏旨在分享记录每日学习的前端知识和学习笔记的归纳总结&#xff0c;欢迎大家在评论区交流讨论&#xff01; 文章目录 作业 2024.4.3-学习笔记css溢出显示单行文本溢出显示省略号多行文本溢出显示省…

【Android】图解View的工作流程原理

文章目录 入口DecorView如何加载到Window中MeasureSpec MeasureView的测量ViewGroup的测量 LayoutView的layout() Draw1、绘制背景3、绘制View内容4、绘制子View6、绘制装饰 入口 DecorView如何加载到Window中 MeasureSpec 该类是View的内部类&#xff0c;封装View的规格尺寸…

C++资源重复释放问题

这不是自己释放了2次&#xff1b; 可能是类互相引用&#xff0c;有类似现象释放资源时引起&#xff1b;还不太了解&#xff1b; 类对象作为函数参数也会引起&#xff1b; 下面是一个简单示例&#xff1b; #include <iostream> #include <string.h> #include &l…

Spark-Scala语言实战(14)

在之前的文章中&#xff0c;我们学习了如何在spark中使用键值对中的fullOuterJoin&#xff0c;zip&#xff0c;combineByKey三种方法。想了解的朋友可以查看这篇文章。同时&#xff0c;希望我的文章能帮助到你&#xff0c;如果觉得我的文章写的不错&#xff0c;请留下你宝贵的点…

最优算法100例之36-扑克牌顺子

专栏主页:计算机专业基础知识总结(适用于期末复习考研刷题求职面试)系列文章https://blog.csdn.net/seeker1994/category_12585732.html 题目描述 LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)...他随机从中抽出了…

软考113-上午题-【计算机网络】-IPv6、无线网络、Windows命令

一、IPv6 IPv6 具有长达 128 位的地址空间&#xff0c;可以彻底解决 IPv4 地址不足的问题。由于 IPv4 地址是32 位二进制&#xff0c;所能表示的IP 地址个数为 2^32 4 294 967 29640 亿&#xff0c;因而在因特网上约有 40亿个P 地址。 由 32 位的IPv4 升级至 128 位的IPv6&am…

FaaF:利用事实作为评估RAG的函数方法

原文地址&#xff1a;faaf-facts-as-a-function-for-evaluating-rag 2024 年 4 月 5 日 在某些情况下&#xff0c;我们使用其他语言模型来验证RAG的输出结果&#xff0c;但这种方法并未能有效识别出数据生成过程中的错误和缺失。 论文解析 挑战 评估的可靠性和效率&#xff…

PyTorch之计算模型推理时间

一、参考资料 如何测试模型的推理速度 Pytorch 测试模型的推理速度 二、计算PyTorch模型推理时间 1. 计算CPU推理时间 import torch import torchvision import time import tqdm from torchsummary import summarydef calcCPUTime():model torchvision.models.resnet18()…

数据字典

文章目录 一、需求分析二、表设计&#xff08;两张表&#xff09;三、功能实现3.1 数据字典功能3.1.1 列表功能3.1.2 新增数据字典3.1.3 编辑数据字典 3.2 数据字典明细3.2.1 列表功能3.2.2 新增字典明细3.2.3 编辑字典明细 3.3 客户管理功能3.3.1 列表功能3.3.2 新增用户3.3.3…

页表基本原理

页表概念 CPU并不是直接访问物理内存地址&#xff0c;而是通过虚拟地址空间来间接访问物理内存地址&#xff1b;虚拟地址空间是操作系统为每个正在执行的进程分配一个逻辑地址&#xff1b;比如在32位系统(处理器和内存地址总线都是32位)&#xff0c;范围是0~(4G-1)&#xff1b…

docker基础学习指令

文章目录 [toc] docker基础常用指令一、docker 基础命令二、docker 镜像命令1. docker images2. docker search3. docker pull4. docker system df5. docker rmi1. Commit 命令 三、 docker 容器命令1. docker run2. docker logs3. docker top4. docker inspect5. docker cp6. …