选择排序:用C语言打造高效的排序算法

在这里插入图片描述

本篇博客会讲解如何使用C语言实现选择排序。

下面我来画图讲解选择排序的思路。

假设有一个数组,其初始状态如下,我们想把这个数组排成升序。
在这里插入图片描述
首先我们标明范围,即[begin, end],一开始begin(b)和end(e)分别表示数组的第一个位置和最后一个位置,我们要找到[begin, end]中的最小的数据(1)和最大的数据(5),并且把最小的数据换到最左边,最大的数据换到最右边。

交换前:
在这里插入图片描述

交换后:
在这里插入图片描述
此时两边的数据就排好了,接下来需要排中间的n-2个数据,我们分别让begin和end向中间走一步,重复刚刚的操作,找出[begin, end]中最小的数(2)和最大的数(4),分别换到最左边和最右边:

交换前:
在这里插入图片描述
交换后:
在这里插入图片描述

接着再让begin和end往中间走,重复上面的步骤,直到begin和end相遇为止。

需要注意的是,在把最小的数据往左边换时,如果最左边的数据刚好是最大的数据,交换之后,最大的数据的位置就变了,此时需要更新最大的数据的位置。

对于选择排序,每一趟选出最小数和最大数的遍历次数是逐渐减少的,每次减少2,其总次数是一个公差为2的等差数列求和,其时间复杂度为O(N2)。由于选择排序消耗常数的额外空间,所以其空间复杂度为O(1)。

下面来讨论选择排序的稳定性。选择排序是非常具有误导性的,很多人可能会认为选择排序是一个稳定的排序,事实上是不稳定的,下面我举一个反例。假设一个数组的初始状态如下:
在这里插入图片描述
当我们把最小数(2)与最左边的数据交换时,会改变两个3的相对顺序。所以,选择排序有可能会改变相同的数据的相对顺序,故选择排序是不稳定的。

代码如下:

void SelectSort(int* a, int n)
{assert(a);int begin = 0;int end = n - 1;while (begin < end){// 找出[begin, end]的最小值和最大值的下标int maxi, mini;maxi = mini = begin;for (int i = begin + 1; i <= end; ++i){if (a[i] > a[maxi]){maxi = i;}if (a[i] < a[mini]){mini = i;}}// 分别把最小值和最大值换到两边Swap(a + mini, a + begin);// 如果最左边本来就是最大值,就被换走了,需要修正maxiif (begin == maxi){maxi = mini;}Swap(a + maxi, a + end);++begin;--end;}
}

总结

选择排序使用一种“选数”的思路,其方法简单粗暴,通过遍历的方式每次找出最小数和最大数,并将其分别换到最左边和最右边。其时间复杂度为O(N2),空间复杂度为O(1)。选择排序是不稳定的。

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

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

相关文章

UE4/5Niagara粒子特效之Niagara_Particles官方案例:3.3->4.3

目录 3.3 Visibility Tag 左边的发射器&#xff1a; 发射器更新 粒子生成 粒子更新 右边的发射器 和左边发射器不同的地方 3.4 Texture Sampling 发射器更新 粒子生成 粒子更新 4.1Play Audio Per Particle 系统 第三个发射器 发射器更新 粒子生成 粒子更新 第二个…

第一个VUE程序?

<!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title></head> <body><div id"app">{{message}} </div><!-- 1.导入Vue.js --> <script s…

【C进阶】指针(一)

大家好&#xff0c;我是深鱼~ 【前言】&#xff1a; 指针的主题&#xff0c;在初阶指针章节已经接触过了&#xff0c;我们知道了指针的概念&#xff1a; 1.指针就是个变量&#xff0c;用来存放地址&#xff0c;地址的唯一标识一块内存空间&#xff08;指针变量&#xff09;&a…

无涯教程-机器学习 - 数据加载

假设如果要启动ML项目&#xff0c;那么您需要做的第一件事也是最重要的事情是什么?这是无涯教程启动任何ML项目都需要加载的数据。关于数据&#xff0c;对于ML项目&#xff0c;最常见的数据格式是CSV(逗号分隔值)。 基本上&#xff0c;CSV是一种简单的文件格式&#xff0c;用…

RocketMQ同步复制和异步复制

如果一个Broker组有Master和Slave&#xff0c;消息需要从Master复制到Slave上&#xff0c;有同步和异步两种复制方式。 1)同步复制 同步复制方式是等Master和Slave均写成功后才反馈给客户端写成功状态&#xff1b; 在同步复制方式下&#xff0c;如果Master出故障&#xff0c…

【数据结构】如何用栈实现队列?图文解析(LeetCode)

LeetCode链接&#xff1a;232. 用栈实现队列 - 力扣&#xff08;LeetCode&#xff09; 注&#xff1a;本文默认读者已掌握栈与队列的基本操作 可以看这篇文章熟悉知识点&#xff1a;【数据结构】栈与队列_字节连结的博客-CSDN博客 目录 做题思路 代码实现 1. MyQueue 2. …

【Python】从入门到上头—Python基础(2)

文章目录 一.基础语法1.编码2.标识符3.保留字4.注释5.行与缩进6.多行语句7.数字(Number)类型8.字符串(String)9.空行10.等待用户输入11.同一行显示多条语句12.多个语句构成代码组13.print 输出14.import 与 from...import 二.基本数据类型1.变量和赋值2.多个变量赋值3.标准数据…

2023.8 -java - 继承

继承就是子类继承父类的特征和行为&#xff0c;使得子类对象&#xff08;实例&#xff09;具有父类的实例域和方法&#xff0c;或子类从父类继承方法&#xff0c;使得子类具有父类相同的行为。 继承的特性 子类拥有父类非 private 的属性、方法。 子类可以拥有自己的属性和方法…

数据库连接池druid 的jar包官网下载-最新版下载

进入官网Central Repository: com/alibaba/druid 往下滑 找到最新版点击进入 找到该jar包 点击即可下载

【HCIP】04.VRRP与BFD

VRRP VRRP基本概念 VRRP路由器 运行VRRP协议的路由器&#xff0c;VRRP是配置在路由器的接口上的&#xff0c;而且也是基于接口来工作的。 VRID 一个VRRP组由多台协同工作的路由器&#xff08;的接口&#xff09;组成&#xff0c;使用相同的VRID&#xff08;Virtual Router…

视频转gif制作怎么制作?视频转gif在线一键转换工具

gif图片可以用于网站和应用程序的界面设计&#xff0c;通过将视频内容转换为gif图像&#xff0c;可以在网站加载过程中显示加载动画、创建交互效果或提供引导&#xff0c;所以今天分享一个快速视频转gif图片&#xff08;https://www.gif.cn&#xff09;的方法&#xff0c;利用视…

API 网关基础

目录 一、网关概述二、网关提供的功能三、常见网关系统3.1 Netflix Zuul3.2 Spring Cloud Gateway3.3 Kong3.4 APISIX3.5 Shenyu 一、网关概述 API网关是一个服务器&#xff0c;是系统的唯一入口。 从面向对象设计的角度看&#xff0c;它与外观模式类似。API网关封装了系统内部…

8、Spring_整合Mybatis

五、Spring整合Mybatis 1.添加依赖 添加依赖 <dependencies><dependency><groupId>org.springframework</groupId><artifactId>spring-context</artifactId><version>5.2.17.RELEASE</version></dependency><depend…

00-音视频-概述

有很多场合会使用的音视频&#xff0c;比如安防、视频闸机、影音播放器、视频通话&#xff0c;短视频等等。 从摄像头采集到用户观看&#xff0c;这中间涉及到了很多技术。 用户一般观看的高清视频1080P30帧。若按24位RGB对视频进行存储&#xff0c;一个60分钟视频所占空间 …

百度工程师浅析解码策略

作者 | Jane 导读 生成式模型的解码方法主要有2类&#xff1a;确定性方法&#xff08;如贪心搜索和波束搜索&#xff09;和随机方法。确定性方法生成的文本通常会不够自然&#xff0c;可能存在重复或过于简单的表达。而随机方法在解码过程中引入了随机性&#xff0c;以便生成更…

什么是数据中心IP,优缺点是什么?

如果根据拥有者或者说发送地址来分类的话&#xff0c;可以将代理分为三类&#xff1a;数据中心ip,住宅ip,移动ip 本文我们来了解数据中心ip的原理以及他们的优势劣势&#xff0c;才能选择适合自己的代理。 一、什么是数据中心ip代理&#xff1f; 数据中心ip是由数据中心拥有…

15. Canvas制作汽车油耗仪表盘

1. 说明 本篇文章在14. 利用Canvas组件制作时钟的基础上进行一些更改&#xff0c;想查看全面的代码可以点击链接查看即可。 效果展示&#xff1a; 2. 整体代码 import QtQuick 2.15 import QtQuick.Controls 2.15Item{id:rootimplicitWidth: 400implicitHeight: implicitWi…

精准高效农业作业,植保无人机显身手

中国作为农业大国&#xff0c;拥有约18亿亩的农田&#xff0c;每年都需要进行种子喷洒和农药施用等农业作业&#xff0c;对于普通农户来说&#xff0c;这是一项耗时耗力的工程&#xff0c;同时&#xff0c;人工喷洒农药极易造成农药慢性中毒&#xff0c;对农民的身体健康产生极…

Unity3D软件安装包分享(附安装教程)

目录 一、软件简介 二、软件下载 一、软件简介 Unity3D是一款全球知名的游戏开发引擎&#xff0c;由Unity Technologies公司开发。它提供了一个跨平台、多功能的开发环境&#xff0c;支持创建2D和3D游戏、交互式应用、虚拟现实、增强现实等多种类型的应用程序。以下是Unity3D…

ChatGPT在高等教育中的应用利弊探讨

​人工智能在教育领域的应用日益广泛。2022年11月OpenAI开发的聊天机器人ChatGPT在全球范围内流传开来&#xff0c;其中用户数量最多的国家是美国(15.22%)。由于ChatGPT应用广泛&#xff0c;具有类似人类回答问题的能力&#xff0c;它正在成为许多学生和教育工作者的可信赖伙伴…