排序算法1
排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。
常见的内部排序算法有:插入排序、希尔排序、选择排序、冒泡排序、归并排序、快速排序、堆排序、基数排序等。概括:
关于时间复杂度
平方阶 (O(n2)) 排序 各类简单排序:直接插入、直接选择和冒泡排序。
线性对数阶 (O(nlog2n)) 排序、快速排序、堆排序和归并排序;
O(n1+§)) 排序,§ 是介于 0 和 1 之间的常数。
希尔排序线性阶 (O(n)) 排序,基数排序,此外还有桶、箱排序。
关于稳定性
排序后 2 个相等键值的顺序和排序之前它们的顺序相同。
稳定的排序算法:冒泡排序、插入排序、归并排序和基数排序。
不是稳定的排序算法:选择排序、快速排序、希尔排序、堆排序。
名词解释
n:数据规模
k:“桶”的个数
In-place:占用常数内存,不占用额外内存
Out-place:占用额外内存
先从蓝桥一道算法题切入
蓝桥题库3225
测试输入
5
1 5 9 3 7
测试输出
1 3 5 7 9
1、冒泡排序
冒泡排序是一种通过不断比较和交换相邻元素来将数列按升序排列的简单算法。其名称源自于较小元素会逐渐“浮”到数列顶部的过程。尽管冒泡排序易于理解和实现,但它的效率较低,尤其是对大数据集。为了提高效率,可以引入一个标志变量(flag),如果在一次完整的遍历中没有发生任何交换,则表明数列已经有序,从而提前结束排序过程。这种优化虽然能在一定程度上减少不必要的比较次数,但对于整体性能的提升并不显著。
算法步骤
- 比较相邻的元素。如果第一个比第二个大,就交换他们两个。
- 对每一对相邻元素作同样的工作,从开始第一对到结尾的最后一对。这步做完后,最后的元素会是最大的数。
- 针对所有的元素重复以上的步骤,除了最后一个。(执行n-1轮)
- 持续每次对越来越少的元素重复上面的步骤,直到没有任何一对数字需要比较。
Python 代码
n = int(input())
li = list(map(int,input().split()))
# 冒泡排序
# 执行n-1轮
for i in range(1,n):
# 第i次从a[0]到a[n-i-1] 列表下标从0开始
for j in range(n-i):
# 每一次循环选出第i大的数,升序,冒出当前最大的泡泡
if li[j]>li[j+1]:
li[j],li[j+1] = li[j+1],li[j]
print(' '.join(map(str,li)))
通过输入样例,从每轮的结果来看看冒泡排序
n = int(input())
'''
5
1 5 9 3 7'''
li = list(map(int,input().split()))
# 冒泡排序
# 执行n-1轮
for i in range(1,n):
# 第i次从a[0]到a[n-i-1] 列表下标从0开始
for j in range(n-i):
# 每一次循环选出第i大的数,升序,冒出当前最大的泡泡
if li[j]>li[j+1]:
li[j],li[j+1] = li[j+1],li[j]
# 看得更直观,打印每轮的结果
print(li)
print(' '.join(map(str,li)))
2、选择排序
选择排序(Selection Sort)是一种简单直观的排序算法,其基本思想是每次从未排序的部分中选出最小(或最大)的元素,放到已排序部分的末尾。尽管选择排序的时间复杂度为 O(n²),在数据规模较小时仍有一定的应用价值,因为它不占用额外的内存空间。
算法步骤
- 首先在未排序序列中找到最小(大)元素,存放到排序序列的起始位置。
- 再从剩余未排序元素中继续寻找最小(大)元素,然后放到已排序序列的末尾。
- 重复第二步,直到所有元素均排序完毕。
Python 代码
n = int(input())
li = list(map(int,input().split()))
# 选择排序
for i in range(n-1):
# 以升序为例,第i次从a[i]到a[n-1]找最小元素放到序列最前面
# i从0开始,每次找第i小的数
min_value = li[i]
min_idx = i
# 往后遍历未排序部分,
for j in range(i,n):
if li[j] < min_value:
# 更新min_value
min_value = li[j]
min_idx = j
# 此时,a[min_idx]更新成为 每次比较都是相邻的两个比
li[i],li[min_idx] = li[min_idx],li[i]
print(' '.join(map(str,li)))
3、插入排序
插入排序的代码实现虽然没有冒泡排序和选择排序那么简单粗暴,但它的原理应该是最容易理解的了,其基本思想是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入,打过扑克牌的话,可以类比一下我们刚拿到手牌时顺牌的情景。插入排序和冒泡排序一样,也有一种优化算法,叫做拆半插入,这里要结合二分去理解。
算法步骤
将待排序序列第一个元素看做一个有序序列,把第二个元素到最后一个元素当成是未排序序列。
从后往前依次扫描未排序序列,将扫描到的每个元素插入有序序列的适当位置。(如果待插入的元素与有序序列中的某个元素相等,则将待插入元素插入到相等元素的后面。)
Python 代码
n = int(input())
li = list(map(int,input().split()))
# 插入排序
# 对于第i个数字,在区间[0,i-1]中 从后往前 找对应插入的位置
for i in range(1,n):
# 抽出来的元素 对应提到的占用额外空间O(1)
value = li[i]
# 插入元素的下标 一开始默认li[1]和li[0]去比,选出li[0]的合适人选
insert_idx = 0
for j in range(i-1,-1,-1):
# 如果遍历到的li[j]大于value,就把li[j]往后挪一位
# 注意是从后往前排,从后往前找
if li[j]>value:
li[j+1] = li[j]
else:
# 找到合适的位置
insert_idx = j+1
break
# 插入第i个数字到已排序数组中
li[insert_idx] = value
print(' '.join(map(str,li)))
相关文章:
排序算法1
排序算法是《数据结构与算法》中最基本的算法之一。 排序算法可以分为内部排序和外部排序,内部排序是数据记录在内存中进行排序,而外部排序是因排序的数据很大,一次不能容纳全部的排序记录,在排序过程中需要访问外存。 常见的内部…...
vector, list 模拟实现
vector 实现 成员属性/迭代器 template<class T> class vector { public:typedef T* iterator;typedef const T* const_iterator;iterator begin() {return _first; }iterator end() {return _end; }const_iterator begin() const {return _first; }const_iterator end…...
中国近代传奇战役
军事战略层面的传奇战役 孟良崮战役:1947年5月,陈毅、粟裕指挥华东野战军在山东孟良崮地区对国民党军进行的一次大规模山地运动歼灭战。此役,我军出其不意地对国民党最强大的王牌之首第七十四师开战,并将其全歼。战役中ÿ…...
微信小程序页面配置详解:从入门到精通
微信小程序页面配置详解:从入门到精通 引言 随着移动互联网的飞速发展,微信小程序作为一种新兴的应用形式,因其便捷性和丰富的功能而受到广泛欢迎。在小程序的开发过程中,页面配置是至关重要的一环。本文将深入探讨微信小程序的页面配置,帮助开发者从基础到高级逐步掌握…...
C#基础题
6.在屏幕上输出如下所示数列:1 1 2 3 5 8 13 21……an(an<10000) 7.求任意两个整数之间所有整数的平方和?(要求从键盘输入任意两个整数,调用已定义函数求和) 8.将一个二维数组行和列元素互换,存…...
前端开发中v-if 与v-show的区别
v-if v-if指令用于条件性地渲染一块内容。这个块只有当指令的表达式返回true时才会被渲染。 工作原理:v-if通过动态地创建和销毁元素来控制元素的显示与隐藏。当条件为false时,对应的元素及其绑定的事件监听器和子组件都会被销毁;当条件…...
Django实现智能问答助手-基础配置
设置 Django 项目、创建应用、定义模型和视图、实现问答逻辑,并设计用户界面。下面是一步一步的简要说明: 目录: QnAAssistant/ # 项目目录 │ ├── QnAAssistant/ # 项目文件夹 │ ├── init.py # 空文件 │ ├── settings.py # 项目配…...
2024-11-25 二叉树的定义
一、基本概念 1.二叉树是n(n>0)个结点的有限集合: ① 或者为空二叉树,即n0。 ②或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成。左子树和右子树又分别是一棵二叉树。 特点: ①每个结点至多只有两棵子树。 ②左右子树不能颠倒&am…...
构建高效 Redis 集群:从问题排查到最佳实践20241125
引言:Redis 集群的重要性 Redis 作为一款高性能的内存数据库,常用于高并发场景,比如缓存、消息队列和排行榜。通过构建 Redis 集群,可以进一步提升可用性与性能。然而,集群的部署并非一帆风顺,常会遇到各种…...
MyBatis多表映射
一、多表映射概念: 1.多表查询结果映射思路: MyBatis思想是:数据库不可能永远是你所想或所需的那个样子。 我们希望每个数据库都具备良好的第三范式或BCNF范式,可惜它们并不都是那样。 如果能有一种数据库映射模式,完美适配所有的应用程序查询需求&…...
[M最短路] lc743. 网络延迟时间(spfa最短路+单源最短路)
文章目录 1. 题目来源2. 题目解析 1. 题目来源 链接:743. 网络延迟时间 相关链接: [图最短路模板] 五大最短路常用模板) 2. 题目解析 怎么讲呢,挺抽象的…很久没写最短路算法了。反正也是写出来了,但脱离了模板,把…...
使用nvm下载多个版本node后提示vue不是内部或外部命令,执行vue create报.vuerc错误
一、使用nvm后执行含vue的相关命令提示vue不是内部或外部命令 前言:之前有项目需要切换node版本,我把node卸载了然后使用nvm下载多个版本的node。现在想通过vue create搭建vue2的项目时提示vue不是内部或外部命令,执行npm i vue/cli后仍然无…...
高端服务器可以防护哪些攻击?
高端服务器,尤其是那些专门设计用于防御网络攻击的高防服务器,能够提供多种层次的防护,以抵御不同类型的网络攻击。以下是高端服务器可以防御的主要攻击类型: 1. DDoS攻击(分布式拒绝服务攻击) 带宽消耗攻…...
助力花生作物智能化采摘,基于嵌入式端超轻量级模型LeYOLO全系列【n/s/m/l】参数模型开发构建花生种植采摘场景下花生果实智能检测计数系统
秋天,是大地回馈辛勤耕耘者的季节,金黄的稻田、硕果累累的果园、还有那一片片郁郁葱葱的花生地,共同绘制出一幅幅丰收的画卷。对于农民而言,秋收不仅仅是收获的季节,更是他们与土地情感交织、汗水与希望交织的见证。花…...
物联网无线局域网WiFi开发(二):WiFi_RTOS_SDK
一、编译工程模板 (一)搭建app目录 在SDK目录下新建app目录 cd 到examples目录下 拷贝smart_config下所有文件到app目录下 cd 到app目录下查看文件是否拷贝成功 (二)修改gen_misc.sh vim 打开gen_misc.sh进行编辑 修改SDK_PATH为当前SDK路径…...
GitLab|应用部署
创建docker-compose.yaml文件 输入docker-compose配置 version: 3.8 services:gitlab:image: gitlab/gitlab-ce:15.11.2-ce.0restart: alwayscontainer_name: gitlab-ceprivileged: truehostname: 192.168.44.235environment:TZ: Asia/ShanghaiGITLAB_OMNIBUS_CONFIG: |exter…...
替换Nacos的MySQL驱动
前言:替换Nacos的MySQL驱动能实现使Nacos支持MySQL8.0及以上版本的MySQL数据库 注:下述教程会使用命令先解压Nacos的jar包然后重新用命令把Nacos压缩成jar包,不然直接用压缩工具替换MySQL驱动后的Nacos是会启动不起来的(因为没有替…...
链表内指定区间反转
描述 将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转,要求时间复杂度 O(n)O(n),空间复杂度 O(1)O(1)。 例如: 给出的链表为 1→2→3→4→5→NULL1→2→3→4→5→NULL, m2,n4m2,n4, 返回 1→4→3→2→5→NULL1→4→3→2→5→NULL. …...
jmeter5.6.3安装教程
一、官网下载 需要提前配置好jdk的环境变量 jmeter官网:https://jmeter.apache.org/download_jmeter.cgi 选择点击二进制的zip文件 下载成功后,默认解压下一步,更改安装路径就行(我安装在D盘) 实用jmeter的bin目录作为系统变量 然后把这…...
JavaScript高级程序设计基础(五)
上接语言基础:JavaScript高级程序设计基础(四) 本节内容较简单,有一定语言基础的可以跳过 2.5 语句 2.5.1 if语句 具体作用不做过多赘述。需要注意的是,在判断条件里会自动调用Boolean();并且在执行语句…...
Stable Diffusion 3 部署笔记
SD3下载地址:https://huggingface.co/stabilityai/stable-diffusion-3-medium/tree/main https://huggingface.co/spaces/stabilityai/stable-diffusion-3-medium comfyui 教程: 深度测评:SD3模型表现如何?实用教程助你玩转Stabl…...
深度解析:Vue 自定义指令到底是什么?快来了解
自定义指令的概述 在Vue中,自定义指令是开发者自定义的,用来在DOM元素上执行特定操作的功能。Vue本身提供了多种内建指令(如v-bind, v-model, v-for, v-if等),但有时候我们需要创建自己的指令来实现一些特殊功能。这些功能可以是对DOM的直接操作,或者是为了满足特定的业…...
CVE-2022-4230
打开什么都没有 使用dirsearch扫描到一个wp-admin 访问wp-admin是一个登陆页面 账号密码都在标题中 登陆后是这个页面 在WP Statistics < 13.2.9 – 经过身份验证的 SQLi |CVE 2022-4230 |插件漏洞 (wpscan.com)中,里边有一段对漏洞的描述。 https://wpscan.com…...
什么是 WPF 中的依赖属性?有什么作用?
依赖属性(Dependency Property)是 WPF 的一个核心概念,它为传统的 .NET 属性提供了增强功能,支持绑定、样式、动画和默认值等功能。通过依赖属性,WPF 提供了一种灵活的数据驱动的方式来处理 UI 属性。 1. 什么是依赖属…...
『 Linux 』网络层 - IP协议 (二)
文章目录 路由NAT技术分片与组装分片的组装IP协议分片的短板 路由 通常情况路由器具备了一个非常重要的功能,即构建子网; 同时路由器需要实现跨网络通信,说明路由器必须存在两个或以上的IP地址,通常在路由器中可以看到几个接口,分别是一个WAN口和几个LAN口; WAN口IP被称为公网I…...
Linux开发者的CI/CD(11)jenkins变量
文章目录 1. **环境变量 (Environment Variables)**常见的环境变量:示例:2. **构建参数 (Build Parameters)**常见的构建参数类型:示例:3 **在 `stages` 块内定义局部变量**示例:使用 `script` 步骤定义局部变量4 变量引用陷阱在 Jenkins 中,变量是自动化流程中非常重要的…...
Python和R荧光分光光度法
🌵Python片段 Python在处理荧光分光光度法数据方面非常强大,得益于其丰富的数据处理和可视化库,可以轻松实现从数据读取到分析的完整流程。荧光分光光度法用于测量物质在激发光照射下发出的荧光强度,常用于定量分析和特性研究。 …...
理解clickhouse 里的分区和分片键区别
文章目录 分片分区两分片,0副本的cluster 分片 CREATE TABLE logs_distributed AS logs_local ENGINE Distributed(cluster_name, -- 集群名称database_name, -- 数据库名称logs_local, -- 本地表名cityHash64(user_id) -- 分片键…...
【数据结构笔记】习题
渐进分析 【2010-THU-Mid】f(n) O(g(n)),当且仅当g(n) Ω(f(n))。(√) 【2010-THU-Mid】若f(n) O(n^2)且g(n) O(n),则以下结论正确的是(AD) A. f(n) g(n) O(n^2) B. f(n) / g(n) O(n) C. g(n) O(f(…...
非交换几何与黎曼ζ函数:数学中的一场革命性对话
非交换几何与黎曼ζ函数:数学中的一场革命性对话 非交换几何(Noncommutative Geometry, NCG)是数学的一个分支领域,它将经典的几何概念扩展到非交换代数的框架中。非交换代数是一种结合代数,其中乘积不是交换性的&…...
【c++】模板详解(2)
🌟🌟作者主页:ephemerals__ 🌟🌟所属专栏:C 目录 前言 一、非类型模板参数 二、模板的特化 1. 概念 2. 场景举例 3. 函数模板的特化 4. 类模板的特化 全特化 偏特化 1. 部分特化 2. 对参数的…...
DICOM图像处理:深入解析DICOM彩色图像中的Planar配置及其对像素数据解析处理的实现
引言 在DICOM(Digital Imaging and Communications in Medicine)标准中,彩色图像的存储与显示涉及多个关键属性,其中**Planar Configuration(平面配置)**属性(标签 (0028,0006))尤为重要。当遇到彩色DICOM图像在浏览时被错误地分割为9张小图,而实际应显示为一…...
【青牛科技】D3308 一块带有 ALC 的双通道前置放大器。它适用于立体声收录机和盒式录音机。
概述: D3308 是一块带有 ALC 的双通道前置放大器。它适用于立体声收录机和盒式录音机。采用 SIP9、SOP14 的封装形式封装。 主要特点: 带内置 ALC 回路的双通道均衡放大器。 低噪声: VNI1.0V(典型值)。 开环…...
goframe开发一个企业网站 MongoDB 完整工具包18
1. MongoDB 工具包完整实现 (mongodb.go) package mongodbimport ("context""fmt""time""github.com/gogf/gf/v2/frame/g""go.mongodb.org/mongo-driver/mongo""go.mongodb.org/mongo-driver/mongo/options" )va…...
自动驾驶3D目标检测综述(四)
前三篇分别介绍了前四章的内容: 第一篇(介绍、摘要和背景):自动驾驶3D目标检测综述(一)_3d 目标检测-CSDN博客 第二篇(第三章 基于激光雷达的3D目标检测):自动驾驶3D目…...
远程控制软件:探究云计算和人工智能的融合
在数字化时代,远程控制工具已成为我们工作与生活的重要部分。用户能够通过网络远程操作和管理另一台计算机,极大地提升了工作效率和便捷性。随着人工智能(AI)和云计算技术的飞速发展,远程控制工具也迎来了新的发展机遇…...
3ds Max2024软件详细安装教程+中文安装包(永久使用)
[名称]:3ds Max2024 [大小]:5.07GB [语言]:简体中文 [安装环境]:Win11/Win10 软件介绍 3DS Max是一款三维建模和渲染软件,可以创造宏伟的游戏世界,布置精彩绝伦的场景以实现设计可视化,并打造身临其境的虚拟现实 (VR) ...在广告…...
深入解析 Spring MVC:架构、组件与最佳实践
文章目录 1. **DispatcherServlet**2. **HandlerMapping**3. **HandlerAdapter**4. **Controller**5. **ModelAndView**6. **ViewResolver**7. **View** 工作流程配置方式XML 配置Java 配置 最佳实践示例项目项目目录结构控制器 (HelloWorldController.java)服务层 (HelloWorld…...
专题二十三_动态规划_回文串系列问题_算法专题详细总结
目录 动态规划 回文串系列问题 1. 回⽂⼦串(medium) 解析: 解决回文串问题,这里提供三个思路: 1.中心扩展法:n^2 / 1 2.马拉车算法:n / n 3.动态规划算法:n^2 / n^2 1.状态表…...
Linux操作系统学习---初识环境变量
目录 编辑 环境变量的概念: 小插曲:main函数的第一、二个参数 获取环境变量信息: 1.main函数的第三个参数 2.查看单个环境变量 3.c语言库函数getenv() 和环境变量相关的操作指令: 1.export---导出环境变量: 2.unse…...
通过map文件了解堆栈分配(STM32、MDK5)--避免堆栈溢出
在最近的一个项目的开发中,每当调用到一个函数,程序就直接跑飞。debug跟进去看不出什么逻辑错误,但发现函数内局部变量声明之后,全局变量的值被清零,后来查看局部变量地址已经超出栈的范围,于是确定是栈溢出。如果不稍微了解一下堆栈,在开发过程中可能碰到各种奇怪的错误…...
设计模式——状态模式
定义 状态模式(State Pattern)是一种行为设计模式。它允许一个对象在其内部状态改变时改变它的行为。对象看起来好像修改了它的类,从直观上看,就像是对象根据自身的状态来动态地切换行为方式。 结构组成 环境(Conte…...
没有技术背景考软考高级选什么科目呀?
没有技术背景的外行小白特别推荐考取 信息系统项目管理师 ,也就是软考高项! 软考高项是软考高级资格考试中相对最容易的一门,同时也是报考人数最多的一门。 为什么选择软考高项呢? 以我自己的经历为例。 刚进入职场时…...
大语言模型---梯度的简单介绍;梯度的定义;梯度计算的方法
1. 梯度介绍 如果我们在一座山上(一个山的坡度有很多,陡峭的,平缓的),想要从山顶下山。而梯度就像告诉我们如何沿着最陡的下坡路线走,以尽快到达山脚(最低点)。 2. 梯度的定义 梯度…...
【R语言管理】Pycharm配置R语言及使用Anaconda管理R语言虚拟环境
目录 使用Anaconda创建R语言虚拟环境1. 安装Anaconda2. 创建R语言虚拟环境 Pycharm配置R语言1. 安装Pycharm2. R Language for IntelliJ插件 参考 使用Anaconda创建R语言虚拟环境 1. 安装Anaconda Anaconda的安装可参见另一博客-【Python环境管理工具】Anaconda安装及使用教程…...
蓝桥杯每日真题 - 第24天
题目:(货物摆放) 题目描述(12届 C&C B组D题) 解题思路: 这道题的核心是求因数以及枚举验证。具体步骤如下: 因数分解: 通过逐一尝试小于等于的数,找到 n 的所有因数…...
mac 如何查看 export NVM_NODEJS_ORG_MIRROR=https://npm.taobao.org/mirrors/node 是否正确
在 macOS 上,如果你想查看环境变量 NVM_NODEJS_ORG_MIRROR 是否已正确设置为 https://npm.taobao.org/mirrors/node,你可以按照以下步骤进行检查: 1. 检查当前环境变量值 打开终端并运行以下命令来查看 NVM_NODEJS_ORG_MIRROR 环境变量的当…...
Android 单元测试的各种环境问题记录
报错记录 failed to configure packages targetSdkVersion failed to configure com.demo.test.SettingsActivityTest.testOnCreate_withNullSavedInstanceState: Package targetSdkVersion34 > maxSdkVersion32 java.lang.IllegalArgumentException: failed to configure …...
选择使用whisper.cpp进行语音转文字
需要将一些wav格式的语音文件转成文字(ASR,STT),接到这个任务后,首先上网搜索有没有现成免费的工具或服务可以使用。常用的关键字如“语音转文字 免费 在线”。 搜到的很多野鸡网站,都可以免注册免费提供短…...
推荐一款网络调试工具:常用网络调试工具2024秋季版(1.1.5.41115)
常用网络调试工具2024秋季版(1.1.5.41115) 此应用程序支持TCP/IP Server、TCP/IP Client、UDP/IP数据收发、文本模式发送与接收、HEX模式发送与接收、报文模式,数据模式,数据管理功能,数据导出至EXCEL报表、存贮于数据库。具体功能如下&#…...