【十大排序算法】----选择排序(详细图解分析+实现,小白一看就会)


目录

一:选择排序——原理

二:选择排序——分析

三:选择排序——实现

四:选择排序——优化

五:选择排序——效率


一:选择排序——原理

        选择排序的原理:通过遍历数组,选出该数组中较大的或者较小的,放在数组的起始位置,当遍历完整个数组时排序完成。

二:选择排序——分析

选择排序的核心就是:多趟选择

若以升序(从小到大)排序为例,假若有N个数。

  • 第一趟遍历的目的是找到整个序列中最小的值,找到之后将其与第一个数(动图中的第0个位置)交换,这样一来,在整个数组中第一个数就是最小的。
  • 第二趟遍历:目的是找到整个序列中次小的值,也就是(动图中第0个位置上的数不在变动,在剩下的 N-1 个数中选出最小的),找到之后将其与剩下的 N-1 个数的第一个数(动图中的第1个位置)交换,这样一来,在整个数组中第一个数(第0位置)就是最小的,第二个数(第1位置)就是次小的
  • ......

当经过 N-1 趟的遍历交换之后,该序列就实现的从小到大的排列了。

 动图如下:  

三:选择排序——实现

选择排序代码实现如下  

#include<stdio.h>void SelectSort1(int* a, int n)            // 传的参数是 整个数组 和 此数组的大小
{int begin = 0;while (begin < n)                       // 决定所遍历的趟数{int mini = begin;for (int i = begin; i < n; i++)     // 从begin位置开始遍历{if (a[mini] > a[i])            // 找到较小的值,标记一下{mini = i;}}// 交换较小的值                     // 遍历一趟之后,将较小的值与 ”第一个数“ 进行交换int tem = a[mini];a[mini] = a[begin];a[begin] = tem;begin++;                   // 决定下一次所遍历的起始位置:(第一趟是0,第二趟为1,....)}
}int main()
{int a[] = { 38,45,22,29,13,24,42 };int sz = sizeof(a) / sizeof(a[0]);         // 获取数组大小for (int i = 0; i < n; i++)                // 打印排序前的数组{printf("%d ", a[i]);}printf("\n");SelectSort1(a, sz);                        // 实现选择排序for (int i = 0; i < n; i++)                // 打印排序后的数组{printf("%d ", a[i]);}printf("\n");
}

四:选择排序——优化

        在选择排序中,我们是可以将其优化的,即可以一趟选出两个值,一个最大值一个最小值,然后将其放在序列开头和末尾,这样可以使选择排序的效率快一倍。

选择排序代码优化实现如下 

#include<stdio.h>// 选择排序(优化)
void SelectSort(int* a, int n)
{int begin = 0, end = n - 1;            // begin标记第0位置,end标记最后一个数的位置while (begin < end)                    // 决定所遍历的次数{int maxi = begin;                  // 较大数---maxi变量标记int mini = begin;                  // 较小数---mini变量标记for (int i = begin; i <= end; i++)    // 在 [begin,end] 这一区间进行遍历{if (a[i] > a[maxi])            // 遍历的数较大,maxi进行标记{maxi = i;}if (a[i] < a[mini])            // 遍历的数较小,mini进行标记{mini = i;}}Swap(&a[begin], &a[mini]);        // 较小的数与 ”第一个数“ 交换,把较小的数放到 ”第一个位置“if (begin == maxi)                // 若 ”第一个位置“ 是较大数的位置,防止这个位置被上一个交换所 ”赶跑“{maxi = mini;}Swap(&a[end], &a[maxi]);        // 较大的数与 ”最后一个数“ 交换,把较大的数放到 ”最后一个位置“ 上++begin;                        // 决定下一次遍历的区间--end;}}int main()
{int a[] = { 38,45,22,29,13,24,42 };int sz = sizeof(a) / sizeof(a[0]);         // 获取数组大小for (int i = 0; i < n; i++)                // 打印排序前的数组{printf("%d ", a[i]);}printf("\n");SelectSort(a, sz);                        // 实现选择排序for (int i = 0; i < n; i++)                // 打印排序后的数组{printf("%d ", a[i]);}printf("\n");
}

        时刻谨记:当一个数已经知道其是 最大/最小 ,并已经将其进行交换之后,那么这个位置是万万不可变动的。

五:选择排序——效率

时间复杂度:O(N^2)

空间复杂度:O(1)

选择排序是不稳定的排序。

选择排序是最简单的排序之一,最大的优点就是好理解,不过因为其效率低下,所以在一般情况下不使用。


        以上的内容若是对大家起到帮助的话,大家可以动动小手点赞,评论+收藏。大家的支持就是我进步路上的最大动力! 

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

精酿啤酒:精酿文化的传承者与创新者

在啤酒的世界中&#xff0c;精酿啤酒是一种与众不同的文化现象。这种文化源于对啤酒品质的追求和对传统工艺的尊重&#xff0c;但在不断发展中也不断涌现出创新。作为精酿啤酒的品牌&#xff0c;Fendi club啤酒不仅是这种文化的传承者&#xff0c;更是创新者。 Fendi club啤酒始…

香港电讯高效网络,助力新消费品牌抓住拓展香港市场新风口

自今年初香港与内地全面恢复通关&#xff0c;两地同胞跨境消费热潮持续升温。港人“北上”消费掀起风潮的同时&#xff0c;香港市场也成为内地新消费品牌拓展的热门目标。从糕点、茶饮、连锁餐饮到服饰&#xff0c;越来越多内地品牌进驻香港。新消费品牌要想在香港开设门店&…

QT部分学习笔记

文章目录 1.前言注意问题2.学习历程2.0 创建项目 快捷键&#xff1a;2.1 创建按钮2.2 对象树2.3 调试输出2.4 QT坐标系2.5 信号和槽 3.Qmainwindow3.1 窗口菜单栏创建3.2 工具栏3.3 状态栏3.4 铆接部件3.5 对话框 4. 1.前言 版本&#xff1a; 5.9.9 注意问题 Qstring类型通多…

算法课程笔记——蓝桥云课第11次直播

算法课程笔记——蓝桥云课第11次直播

ORA-28575: unable to open RPC connection to external procedure agent

环境&#xff1a; Oracle 11.2.0.4x64 RAC AIX6.1版本SDE for aix oracle11g版本10.0 x64 sde配置情况如下&#xff1a; 检查oracle和grid用户下的$ORACLE_HOME/hs/admin/extproc.ora文件均包含有如下&#xff1a; SET EXTPROC_DLLSANY 两个节点sde下的user_libraries都正常…

leetcode.环形链表问题

目录 题目1 示例 解题思路 代码实现 补充 题目2 示例 解题思路 代码实现 题目1 该题链接&#xff1a;https://leetcode.cn/problems/linked-list-cycle/description/ 示例 解题思路 要创建两个指针一个是快指针(fast)&#xff0c;另一个慢指针(slow)。快指针走两步慢指…

【Android】Apk图标的提取、相同目录下相同包名提取的不同图标apk但是提取结果相同的bug解决

一般安卓提取apk图标我们有两种常用方法&#xff1a; 1、如果已经获取到 ApplicationInfo 对象&#xff08;假设名为 appInfo&#xff09;&#xff0c;那么我们获取方法为&#xff1a; appInfo.loadIcon(packageManager)// 返回一个 Drawable 对象2、 如果还没获取到 Applica…

必背!!2024年软考中级——网络工程师考前冲刺几页纸

距离软考考试的时间越来越近了&#xff0c;趁着这两周赶紧准备起来 今天给大家整理了——软考网络工程师考前冲刺几页纸&#xff0c;都是核心重点&#xff0c;有PDF版&#xff0c;可打印下来&#xff0c;每天背一点。 计算机总线分类 ①总线的分类&#xff1a;数据总线、地址总…

内网渗透瑞士军刀-impacket工具解析(二)

impacket工具解析之Kerberos认证协议 上一期我们介绍了impacket中ntlm协议的实现&#xff0c;在Windows认证中除了使用ntlm认证&#xff0c;还支持Kerberos认证协议&#xff0c;Kerberos认证也是Windows 活动目录中占比最高的认证方式。 什么是Kerberos协议&#xff1f; Kerb…

CSRF 攻击实验:更改请求方式绕过验证

前言 CSRF&#xff08;Cross-Site Request Forgery&#xff09;&#xff0c;也称为XSRF&#xff0c;是一种安全漏洞&#xff0c;攻击者通过欺骗用户在受信任网站上执行非自愿的操作&#xff0c;以实现未经授权的请求。 CSRF攻击利用了网站对用户提交的请求缺乏充分验证和防范…

英语学习笔记10——Look at ...

Look at … 看…… 词汇 Vocabulary fat adj. 胖的&#xff0c;丰富的 n. 脂肪 例句&#xff1a;他是个胖男孩。    He is a fat boy. 搭配&#xff1a;fat cat 有钱人&#xff0c;土豪 woman n. 女人 girl n. 女孩 madam n. 女士 man n. 男人 boy n. 男孩 sir n. 先生 …

jdk安装多个版本,但是java -version显示最早安装的版本,换掉Path或者JAVA_HOME不生效问题

问题一&#xff1a;当你的电脑上又多个jdk版本&#xff0c;如17 或者8时&#xff0c;使用命令行 java -version显示最早安装的&#xff0c;如下图所示&#xff1a;环境变量配置的17&#xff0c;但是命令行显示的是8。 原因&#xff1a;windows电脑装jdk17后 会在你的环境变量…

声纹识别在无人机探测上的应用

无人机在民用和军事领域的应用越来越广泛。然而&#xff0c;随着无人机数量的增加&#xff0c;"黑飞"现象也日益严重&#xff0c;对公共安全和隐私构成了威胁。因此&#xff0c;开发有效的无人机探测与识别技术变得尤为重要。及时发现黑飞无人机的存在进而对其型号进…

Springboot+Vue项目-基于Java+MySQL的民族婚纱预定系统(附源码+演示视频+LW)

大家好&#xff01;我是程序猿老A&#xff0c;感谢您阅读本文&#xff0c;欢迎一键三连哦。 &#x1f49e;当前专栏&#xff1a;Java毕业设计 精彩专栏推荐&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb;&#x1f447;&#x1f3fb; &#x1f380; Python毕业设计 &…

在浏览器执行js脚本的两种方式

fetch请求get 在浏览器执行http请求,可以使用fetch函数; fetch(“url”).then(response => response.text()) .then(data => console.log(JSON.parse(data)[‘status’])) .catch(error => console.error(error)) 直接返回json数据: fetch(“url”).then(response…

【Java】/*数组的定义与使用*/

目录 一、数组的定义 1.1 为什么要使用数组 1.2 什么是数组 1.3 数组的初始化 1.3.1 动态初始化 1.3.2 静态初始化 1.2.3 注意事项 三、遍历数组 3.1 用循环的方式遍历数组 3.2 用 for each 的方式遍历数组 3.3 用 Arrays.toString 的方式遍历数组 3.4 一些其他的…

【3dmax笔记】028:倒角的使用方法

一、倒角描述 在3dmax中创建倒角效果可以通过多种方法实现,以下是几种常见的方法: 使用倒角修改器。首先创建一个图形(如矩形和圆),然后对齐它们,将它们转化为可编辑样条线,并附加在一起,选择要倒角的边缘,然后使用倒角修改器来调整高度、轮廓等参数。使用倒角剖面修…

【稳定检索|投稿优惠】2024年医学、药学与生物工程国际会议(ICMPB 2024)

2024年医学、药学与生物工程国际会议&#xff08;ICMPB 2024&#xff09; 2024 International Conference on Medicine, Pharmacy, and Biotechnology 【会议简介】 2024年医学、药学与生物工程国际会议将于长沙召开。此次会议将汇聚全球医学、药学与生物工程领域的顶尖学者…

MIT 6.5840(6.824) Lab2:Key/Value Server 设计实现

1 实验要求 在本次 Lab 中&#xff0c;你将在单机上构建一个键/值服务器&#xff0c;以确保即使网络出现故障&#xff0c;每个操作也只能执行一次&#xff0c;并且操作是可线性化的。 客户端可以向键/值服务器发送三个不同的 RPC&#xff1a; Put(key, value) 、 Append(key,…

【Linux】进程间通信(一)---- 匿名管道

【Linux】进程间通信&#xff08;一&#xff09;---- 匿名管道 一.序1什么是进程间通信2.进程间通信的标准3.为什么需要进程通信 二.匿名管道1.原理2.使用3.四种情况4.五个特点 一.序 1什么是进程间通信 进程间通信 通信我们大致知道是啥&#xff0c;就是互相传递信息 那进程…