数据结构 ——— 直接选择排序算法的实现

目录

直接选择排序算法的思想

优化直接选择排序算法的思想

代码实现(默认升序) 


直接选择排序算法的思想

直接选择排序算法的思想类似与直接插入排序
区别在于从大到小选择最小的元素或者最大的元素直接放在元素应该停留的位置
每次从待排序的元素中选出最小或者最大的元素(根据降序或者升序选择)
存放在序列的起始位置,直到全部待排序的数据元素排完为止


优化直接选择排序算法的思想

优化前:

每次从待排序的元素中选出最小或者最大的元素,存放到应该停留的位置,再次选出次大或者次小的数,存放到应该停留的位置,这样做的话每次只能选出一个元素

优化后:

而可以优化的是每次在待排序的元素中选出最大和最小的两个元素,放在各自最后应该停留的位置
再选出次大和次小的元素,放在最后改停留的位置


代码实现(默认升序)

代码演示:

void Swap(int* p1, int* p2)
{int tmp = *p1;*p1 = *p2;*p2 = tmp;
}void SelectSort(int* a, int size)
{int left = 0;int right = size - 1;while (left < right){int min = left;int max = right;for (int i = left; i <= right; i++){if (a[i] < a[min]){min = i;}if (a[i] > a[max]){max = i;}}Swap(&a[left], &a[min]);if (max == left){max = min;}Swap(&a[right], &a[max]);left++;right--;}
}

代码解析:

left 表示数组首元素的下标,right 表示数组尾元素的下标
以排成升序为例
找到数组中最小的元素时就放在下标为 left 的元素处
注意:这里的放入不是直接覆盖首元素,而是和首元素交换
且找到数组中最大的元素时就放在下标为 right 的元素处,同样是交换
再找到数组中次小的元素和次大的元素进行交换………………
每交换一对元素,那么 left 就递增 1 ,而 right 就递减 1
直到 left == right 时,说明所有元素都停留再了最后应该停留的位置
这时的数组就是升序

min 是数组中最小元素的下标,而 max 是数组中最大元素的下标
再通过 left 和 right 为数组的区间来遍历数组,找到最小元素的下标赋值给 min ,找到最大元素的下标赋值给 max
这样做的原因是:因为最开始 left 是 0 ,right 是 size-1,找到了最小和最大的元素后,放在了首尾位置,那么数组首尾位置就不用再遍历了,而且刚好 left 递增了 1,right 递减了 1,如果找到了次大的元素和次小的元素时同样如此,所以用 left 和 right 控制数组的区间刚好合适

找到最小元素的下标 min 时,和首元素的下标 left 交换
找到最大元素的下标 max 时,和尾元素的下标 right 交换
交换时需要注意一种情况,因为是先把最小的元素交换到数组首元素的位置
当如果首元素就是最大的元素时,就会出问题,因为这时的 max 就在首元素的位置
但是已经把最小的元素交换到这里了,而 max 的位置没有更新,那么如果再交换最大元素和尾元素时,就会发生错乱,就会把最小的元素,交换到尾元素去,这样就不能实现升序了
改正的办法是判断 max 是否和 left 相同,如果相同的话,就更新 max 的位置
因为最开始 min 和 left 交换了,所以此时最大的元素就在 min 处,直接把 min 赋值给 max 即可

代码验证:

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

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

相关文章

linux从0到1——shell编程9

声明&#xff01; 学习视频来自B站up主 **泷羽sec** 有兴趣的师傅可以关注一下&#xff0c;如涉及侵权马上删除文章&#xff0c;笔记只是方便各位师傅的学习和探讨&#xff0c;文章所提到的网站以及内容&#xff0c;只做学习交流&#xff0c;其他均与本人以及泷羽sec团队无关&a…

selinux及防火墙

selinux说明 SELinux 是 Security-Enhanced Linux 的缩写&#xff0c;意思是安全强化的 linux 。 SELinux 主要由美国国家安全局&#xff08; NSA &#xff09;开发&#xff0c;当初开发的目的是为了避免资源的误用。 httpd进程标签&#xff08;/usr/share/nginx/html &#…

前端:JavaScript (学习笔记)【2】

目录 一&#xff0c;数组的使用 1&#xff0c;数组的创建 [ ] 2&#xff0c;数组的元素和长度 3&#xff0c;数组的遍历方式 4&#xff0c;数组的常用方法 二&#xff0c;JavaScript中的对象 1&#xff0c;常用对象 &#xff08;1&#xff09;String和java中的Stri…

QML学习 —— 28、3种等待指示控件(附源码)

效果如下 说明 BusyIndicator应用于指示在加载内容或UI被阻止等待资源可用时的活动。BusyIndicator类似于一个不确定的ProgressBar。两者都可以用来指示背景活动。主要区别在于视觉效果,ProgressBar还可以显示具体的进度(当可以确定时)。由于视觉差异,繁忙指示器和不确定的…

Java 基于SpringBoot+Vue的家政服务管理平台

博主介绍&#xff1a;✌程序员徐师兄、7年大厂程序员经历。全网粉丝12w、csdn博客专家、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于Java技术领域和毕业项目实战✌ &#x1f345;文末获取源码联系&#x1f345; &#x1f447;&#x1f3fb; 精彩专栏推荐订阅&#x1f447;…

DataGear 5.2.0 发布,数据可视化分析平台

DataGear 企业版 1.3.0 已发布&#xff0c;欢迎体验&#xff01; http://datagear.tech/pro/ DataGear 5.2.0 发布&#xff0c;图表插件支持定义依赖库、严重 BUG 修复、功能改进、安全增强&#xff0c;具体更新内容如下&#xff1a; 重构&#xff1a;各模块管理功能访问路径…

nature communications论文 解读

题目《Transfer learning with graph neural networks for improved molecular property prediction in the multi-fidelity setting》 这篇文章主要讨论了如何在多保真数据环境&#xff08;multi-fidelity setting&#xff09;下&#xff0c;利用图神经网络&#xff08;GNNs&…

Flutter:SlideTransition位移动画,Interval动画延迟

配置vsync&#xff0c;需要实现一下with SingleTickerProviderStateMixinclass _MyHomePageState extends State<MyHomePage> with SingleTickerProviderStateMixin{// 定义 AnimationControllerlate AnimationController _controller;overridevoid initState() {super.…

svn 崩溃、 cleanup失败 怎么办

在使用svn的过程中&#xff0c;可能出现整个svn崩溃&#xff0c; 例如cleanup 失败的情况&#xff0c;类似于 这时可以下载本贴资源文件并解压。 或者直接访问网站 SQLite Download Page 进行下载 解压后得到 sqlite3.exe 放到发生问题的svn根目录的.svn路径下 右键呼出pow…

GPT系列文章

GPT系列文章 GPT1 GPT1是由OpenAI公司发表在2018年要早于我们之前介绍的所熟知的BERT系列文章。总结&#xff1a;GPT 是一种半监督学习&#xff0c;采用两阶段任务模型&#xff0c;通过使用无监督的 Pre-training 和有监督的 Fine-tuning 来实现强大的自然语言理解。在 Pre-t…

Linux线程(Linux和Windows的线程区别、Linux的线程函数、互斥、同步)

Linux线程&#xff08;Linux和Windows的线程区别、Linux的线程函数、互斥、同步&#xff09; 1. 线程介绍 线程的概念&#xff1a; 线程是 CPU 调度的基本单位。它被包含在进程之中&#xff0c;是进程中的实际运作单位。一条线程指的是进程中一个单一顺序的控制流&#xff0…

Large Spatial Model:End-to-end Unposed Images to Semantic 3D 论文解读

目录 一、概述 二、相关工作 1、SfM和可微神经表示 2、端到端的Image-to-3D 三、LSM 1、密集几何预测 2、2D信息特征提取 3、点特征融合 4、可微渲染 5、损失函数 四、实验 一、概述 该论文提出一种大型空间模型&#xff08;Larget Spatial Model,LSM&#xff09;…

Leetcode207. 课程表(HOT100)

链接 题解&#xff1a;先统计入度为0的点&#xff0c;如果一个节点入度为0&#xff0c;说明没有课程指向它&#xff0c;那么你就可以学习它了。反之说明还有先修课。 注意&#xff1a;图存在拓扑排序等价于图不存在环。其实可以想出&#xff1a;如果是一个环&#xff0c;那么…

JavaScript将至

JS是什么&#xff1f; 是一种运行在客户端&#xff08;浏览器&#xff09;的编程语言&#xff0c;实现人机交互效果 作用捏&#xff1f; 网页特效 (监听用户的一些行为让网页作出对应的反馈) 表单验证 (针对表单数据的合法性进行判断) 数据交互 (获取后台的数据, 渲染到前…

Centos-stream 9,10 add repo

Centos-stream repo前言 Centos-stream 9,10更换在线阿里云创建一键更换repo 自动化脚本 华为centos-stream 源 , 阿里云centos-stream 源 华为epel 源 , 阿里云epel 源vim /centos9_10_repo.sh #!/bin/bash # -*- coding: utf-8 -*- # Author: make.h

网络安全概论

一、 网络安全是一个综合性的技术。在Internet这样的环境中&#xff0c;其本身的目的就是为了提供一种开放式的交互环境&#xff0c;但是为了保护一些秘密信息&#xff0c;网络安全成为了在开放网络环境中必要的技术之一。网络安全技术是随着网络技术的进步逐步发展的。 网络安…

【Android】android compat理解

1&#xff0c;前提 即便是在同一手机上安装的不同apk&#xff0c;其编译的apk不同&#xff0c;也会导致行为上的差异。如SDK34有限制后台启动&#xff0c;但如果安装的apk所依赖的sdk是33&#xff0c;则不会表现出此差异。这是如何实现的呢&#xff1f;其实&#xff0c;本质是…

《数据结构》学习系列——图(中)

系列文章目录 目录 图的遍历深度优先遍历递归算法堆栈算法 广度优先搜索 拓扑排序定义定理算法思想伪代码 关键路径基本概念关键活动有关量数学公式伪代码时间复杂性 图的遍历 从给定连通图的某一顶点出发&#xff0c;沿着一些边访问遍图中所有的顶点&#xff0c;且使每个顶点…

【C++】static修饰的“静态成员函数“--静态成员在哪定义?静态成员函数的作用?

声明为static的类成员称为类的静态成员&#xff0c;用static修饰的成员变量&#xff0c;称之为静态成员变量&#xff1b;用 static修饰的成员函数&#xff0c;称之为静态成员函数。静态成员变量一定要在类外进行初始化 一、静态成员变量 1)特性 所有静态成员为所有类对象所共…

MySQL面试-1

InnoDB中ACID的实现 先说一下原子性是怎么实现的。 事务要么失败&#xff0c;要么成功&#xff0c;不能做一半。聪明的InnoDB&#xff0c;在干活儿之前&#xff0c;先将要做的事情记录到一个叫undo log的日志文件中&#xff0c;如果失败了或者主动rollback&#xff0c;就可以通…