排序算法2
排序算法1-CSDN博客
排序算法1中提及的是较为基础(暴力实现,复杂度较高)的排序算法,不适合于数据量较大的场景,比如序列长度达到1e5
接下来以蓝桥另一道题目来理解其它的排序算法
蓝桥3226
蓝桥账户中心
样例
5
1 5 9 3 7
4、快速排序
快速排序是一种高效的排序算法,采用分治法(Divide and Conquer)(二分思想)策略来对一个序列进行排序。
快速排序的最坏运行情况是 O(n²),比如说顺序数列的快排。但它的平摊期望时间是 O(nlogn),且 O(nlogn) 记号中隐含的常数因子很小,比复杂度稳定等于 O(nlogn) 的归并排序要小很多。所以,对绝大多数顺序性较弱的随机数列而言,快速排序总是优于归并排序。
算法步骤
1. 从数列中挑出一个元素,称为 “基准”(pivot),一般选择乱序数组的第一个元素;
2. 重新排序数列,所有元素比基准值小的摆放在基准前面,所有元素比基准值大的摆在基准的后面(相同的数可以到任一边)。
3.在这个分区退出之后,该基准就处于数列的中间位置。这个称为分区(partition)操作。值得注意的是,从每次‘分区’的过程中看,除了筛选相较于‘基准值’小或者大的数以外,不做额外的排序;
4.递归地(recursive)把小于基准值元素的子数列和大于基准值元素的子数列排序;递归的最底部情形,是数列的大小是零或一,也就是永远都已经被排序好了。
从递归的性质看,递归的结构特点是基于栈的,计算顺序满足‘后进先出’,也就是输入乱序数组后,会每一轮选出一个基准值,然后筛选相较于‘基准值’小或者大的数,小的放入左边序列,大的放入右边序列,之后递归处理这两个序列,基准值在本轮后都不再进入排序过程中,因为本轮结束后,基准值的位置是正确的,后面就是一直递归到两边的排序数组长度都为1,又每一轮都有一个基准值被选出排序的序列,迭代地完成了排序。
# li[left,right]按照小于等于(等于基准值的元素放在左边或者右边都可以)基准值、基准值、大于等于基准值
# 定义一个函数返回每一轮筛选的基准值下标
def num_partition(li,left,right):# left为每一轮基准值的初始化下标# 放置 小于等于 基准值元素的下标idx = left+1# 除选出的序列第一个元素作为基准值,遍历当前序列剩下的元素for i in range(left+1,right+1):if li[i] <= li[left]:# 放左边li[idx],li[i] = li[i],li[idx]# 本轮基准值下标后移1idx += 1# 小于等于本轮基准值的元素为li[left+1,idx-1],上述设定小于等于都放左边li[left],li[idx-1] = li[idx-1],li[left]return idx-1# 基于定义好的返回每轮基准值下标的函数,实现快速排序
def quick_sort(li,left,right):# print(li)# left == right时排序完成if left < right:# 选本轮基准值mid = num_partition(li,left,right)# 基于 二分 的思想# 递归左边quick_sort(li,left,mid-1)# 递归右边quick_sort(li,mid+1,right)n = int(input())
li = list(map(int,input().split()))
quick_sort(li,0,n-1) # n-1:len(li)-1
print(' '.join(map(str,li)))
5、归并排序
归并排序(Merge Sort)是一种基于分治法的比较排序算法,其基本思想是将数组分成两个子数组,分别对这两个子数组进行排序,然后将它们合并成一个有序数组。归并排序在时间复杂度和稳定性方面表现优异。归并排序的实现由两种方法:
- 自上而下的递归(所有递归的方法都可以用迭代重写,所以就有了第 2 种方法);
- 自下而上的递归;
和选择排序一样,归并排序的性能不受输入数据的影响,但表现比选择排序好的多,因为始终都是 O(nlogn) 的时间复杂度。代价是需要额外的内存空间。
算法步骤
1.申请空间,使其大小为两个已经排序序列之和,该空间用来存放合并后的序列;
2.设定两个指针,最初位置分别为两个已经排序序列的起始位置;
3.比较两个指针所指向的元素,选择相对小的元素放入到合并空间,并移动指针到下一位置;
4.重复步骤 3 直到某一指针达到序列尾;
5.将另一序列剩下的所有元素直接复制到合并序列尾。
从输出结果来看归并排序,因为是递归地排序,所以要从后往前看
从树状结构来理解这个递归过程:
# 定义函数:用于合并两个序列。后续merge_sort函数递归调用 把序列一路递归到长度为1的两个来跑merge
def merge(li1,li2):result = []while len(li1)!=0 and len(li2)!=0:if li1[0]<=li2[0]:result.append(li1.pop(0))else:result.append(li2.pop(0))result.extend(li1)result.extend(li2)return resultdef merge_sort(li):# 一路递归到序列剩下一个元素print(li)if len(li)<2:return li# 基于二分的思想mid = len(li)//2left = merge_sort(li[:mid])right = merge_sort(li[mid:])return merge(left,right)n = int(input())
li = list(map(int,input().split()))
print(' '.join(map(str,merge_sort(li))))
6、计数排序
计数排序的核心在于将输入的数据值转化为键存储在额外开辟的数组空间中。作为一种线性时间复杂度的排序,计数排序要求输入的数据必须是有确定范围的整数。
计数排序与桶排序的区别:
1. 基本概念
计数排序:计数排序是一种线性时间复杂度的排序算法,适用于已知范围的整数排序。它通过一个额外的数组来记录每个元素的出现次数,然后根据这些计数重新构建排序后的数组。
桶排序:桶排序是一种分布排序算法,它将元素分布到有限数量的桶中,每个桶再分别排序。所有桶中的元素收集起来以后就是有序的。
2. 适用条件
计数排序:
适用于整数排序。
需要知道输入数据的最小值和最大值。空间复杂度较高,因为需要一个额外的计数数组。时间复杂度为 O(n+k),其中 n 是数据的数量,k 是数据的范围。
桶排序:
适用于任意类型的数据(只要可以比较大小)。
不需要知道输入数据的最小值和最大值。空间复杂度取决于桶的数量和数据分布。时间复杂度为 O(n+k),其中 n 是数据的数量,k 是桶的数量。
3. 实现步骤
计数排序:
找到输入数据中的最小值和最大值。
创建一个计数数组并初始化为零。遍历输入数据,统计每个值的出现次数。根据计数数组重建排序后的数据。
桶排序:
创建若干个空桶。
将输入数据分配到各个桶中。对每个桶进行单独排序。依次从各个桶中取出数据,得到有序的结果。
值得注意的是,如果不通过一些内存的优化策略,使用计数排序会报内存错误。
内存错误(MemoryError) 是因为计数排序需要为数据范围(maxvalue - minvalue + 1)分配一个大小为 O(k) 的数组。当数据的范围(即 maxvalue - minvalue)非常大时,分配的计数数组可能需要超出可用内存。
原因分析
1.数据范围过大: 计数排序创建的 count 数组,其长度为 maxvalue - minvalue + 1,与数据的范围成正比。如果 maxvalue 和 minvalue 之间的差距非常大(比如几百万甚至更大),那么需要创建一个超大数组,导致内存溢出。
2.不是所有数据都连续: 计数排序默认假设数据是连续的。如果输入数据是稀疏的(如 1 和 1000000 之间只有少量值),这种实现方式会浪费大量内存。
示例:
假设输入数据 m = [1, 1000000],那么计数数组的大小会是 1000000 - 1 + 1 = 1000000。即使实际数据量只有 2 个数,仍然会为 100 万个位置分配内存。
一个可行的策略是哈希表代替计数数组,改用一个字典(哈希表)来记录元素的出现次数,这样可以避免为稀疏数据分配多余的空间。
def counting_sort_optimized(m):# 统计每个元素的出现次数count = {}for num in m:if num in count:count[num] += 1else:count[num] = 1# 根据统计结果生成排序后的数组sorted_m = []for key in sorted(count): # 按键值升序排序sorted_m.extend([key] * count[key])return sorted_mn = int(input())
m = list(map(int, input().split()))
a = counting_sort_optimized(m)
print(' '.join(map(str, a)))
7、桶排序
桶排序(Bucket Sort)是一种基于分布的排序算法,也称为箱排序。它通过将数据分到若干个有序的“桶”中,然后对每个桶进行单独排序,最后将所有桶中的数据合并起来得到最终的排序结果。桶排序适用于数据分布均匀且数据量较大的情况,其时间复杂度为 O(n+k),其中 n 是待排序元素的数量,k 是桶的数量。
桶排序是计数排序的升级版。它利用了函数的映射关系,高效与否的关键就在于这个映射函数的确定。为了使桶排序更加高效,我们需要做到这两点:
1.在额外空间充足的情况下,尽量增大桶的数量;
2.使用的映射函数能够将输入的 N 个数据均匀的分配到 K 个桶中。
3.同时,对于桶中元素的排序,选择何种比较排序算法对于性能的影响至关重要。
什么时候最快
当输入的数据可以均匀的分配到每一个桶中。
什么时候最慢
当输入的数据被分配到了同一个桶中。
例子演示:序列[11,22,33,44,45,56,77,88,99]
def bucket_sort(m,bucket_count):# m:序列;bucket_count:多少个桶minvalue,maxvalue = min(m),max(m)# 桶的大小bucket_size = (maxvalue - minvalue+1)// bucket_count+1# 存放每个桶 []代表一个桶res = [[] for _ in range(bucket_count+1)]for i in m: # m个桶idx = (i - minvalue)//bucket_sizeres[idx].append(i)# ans存放排序结果ans = []for res_i in res:res_i.sort()ans += res_ireturn ansn = int(input())
m = list(map(int,input().split()))
a = bucket_sort(m,min(n,10000))
print(' '.join(map(str,a)))
相关文章:

排序算法2
排序算法1-CSDN博客 排序算法1中提及的是较为基础(暴力实现,复杂度较高)的排序算法,不适合于数据量较大的场景,比如序列长度达到1e5 接下来以蓝桥另一道题目来理解其它的排序算法 蓝桥3226 蓝桥账户中心 样例 5 1 5 9 3 7 4、快速排序 快速排…...
【Web开发基础学习——corsheaders 应用的理解】
Web开发基础学习系列文章目录 第一章 基础知识学习之corsheaders 应用的理解 文章目录 Web开发基础学习系列文章目录前言一、使用1.1 安装1.2 配置 二、功能总结 前言 corsheaders 是一个 Django 第三方应用,用于处理跨域资源共享 (CORS)。CORS 是一种机制&#x…...
Redis和MySQL之间如何进行数据同步
原因 为什么要进行Redis和MySQL的数据同步? 性能优化:MySQL是关系型数据库,数据读取和存储相对复杂;Redis是内存数据库,读写速度极快,将热点数据存在Redis,可以大大提高系统的访问速度。 数据…...

css:转换
转换 移动 /* transform: translate(100px, 200px); */transform: translateX(100px);transform: translateY(100px); /*一个意思*/ 如果后面跟百分数的意思是移动盒子自身x/y方向长度的百分比,可以用作子绝父相控制盒子水平居中垂直居中 translate里的xy值是相对…...
状态管理与存储:Vuex 和 sessionStorage
1. sessionStorage 存储位置 sessionStorage 是浏览器提供的 Web Storage API 的一部分,用于在一个会话期间存储数据。数据保存在浏览器的 内存 中,而不是在硬盘上,且其生命周期仅限于当前浏览器标签页。数据在浏览器窗口或标签页关闭时会被…...
Redis和MySQL保持一致性的延迟双删(Delay Double Delete)策略
Redis和MySQL保持一致性的延迟双删(Delay Double Delete)策略,是一种在数据更新或删除时为了保证数据一致性而采取的方法。以下是延迟双删的过程和原理的详细解释: 一、过程 第一次删除缓存: 当需要更新数据库中的数据…...

快速理解微服务中Fegin的概念
一.由来 1.在传统的架构里面,我们是通过使用RestTemplate来访问其他的服务,但是这种方式就存在了一个很大的缺陷,也就是被调用方如果发生了服务的迁移(IP和端口发生了变化),那么调用方也需要同步的在代码里面进行修改,…...

新增工作台模块,任务中心支持一键重跑,MeterSphere开源持续测试工具v3.5版本发布
2024年11月28日,MeterSphere开源持续测试工具正式发布v3.5版本。 在这一版本中,MeterSphere新增工作台模块,工作台可以统一汇总系统数据,提升测试数据的可视化程度并增强对数据的分析能力,为管理者提供测试工作的全局…...

快速搭建一个博客!!!“Halo框架深度优化:搭建你的个性化博客或网站”
目录 引言: 一. 首先服务器上去下载一个docker 1.可以参考官方地址: 2. 通过宝塔来一键安装!!! 3.也可以自己下载!!! 1.卸载旧版 2.配置Docker的yum库 3.安装Docker 4.启动和…...

009 STM32 HAL库介绍
STM32 HAL库(Hardware Abstraction Layer)是STMicroelectronics为STM32系列微控制器提供的一套硬件抽象层库,它旨在简化STM32的开发过程,提高代码的可移植性和可维护性。HAL库通过提供一组统一的API接口,使得开发者无需…...

【微服务】 Eureka和Ribbon
一、Eureka 服务调用出现的问题:在远程调用另一个服务时,我们采用的解决办法是发送一次http请求,每次环境的变更会产生新的地址,所以采用硬编码会出现很多麻烦,并且为了应对并发问题,采用分布式部署&#…...

6.算法移植第六篇 YOLOV5/rknn生成可执行文件部署在RK3568上
接上一篇文章best-sim.rknn模型生成好后,我们要将其转换成可执行文件运行在RK3568上,这一步需要在rknpu上进行,在强调一遍!!rknpu的作用是可以直接生成在开发板上运行的程序 退出上一步的docker环境 exit1.复制best-…...

element的el-table表格标题用css自定义是否必填,用添加伪类的方式标红色*
element的el-table表格标题用css自定义是否必填添加伪类红色 * 效果图如下👇 el-table组件的html部分 css部分 /deep/.el-table__header-wrapper{.el-table__header{.has-gutter tr .el-table__cell:nth-of-type(3) .cell:before{content: *;color:red}.has-gutte…...
数据仓库: 8- 数据仓库性能优化
CSDN 目录展示 目录 8- 数据仓库性能优化8.1 查询优化8.1.1 索引优化8.1.2 分区和分桶8.1.3 使用缓存8.1.4 查询简化与重写8.1.5 聚合优化8.1.6 并行化和分布式计算8.1.7 基于列存储的优化8.1.8 表的分区和数据清洗8.1.9 查询提示 (Hints)8.1.10 自动调优工具 8.2 索引设计8.2…...
可编程网络在分布式深度学习通信瓶颈控制中的应用与未来展望
目录 可编程网络在分布式深度学习通信瓶颈控制中的应用与未来展望 可编程网络在分布式深度学习通信瓶颈控制中的应用与未来展望 在分布式深度学习领域,随着模型规模的不断扩大,训练过程中的通信开销已成为制约性能提升的关键因素。传统的分布式训练方法面临高通信延迟和带宽…...

【论文笔记】Tool Learning with Foundation Models 论文笔记
Tool Learning with Foundation Models 论文笔记 文章目录 Tool Learning with Foundation Models 论文笔记摘要背景:工作: 引言工具学习的发展本文工作(大纲&目录) 背景2.1 工具使用的认知起源2.2 工具分类:用户界…...
Springfox迁移到 Springdoc OpenAPI 3
将项目从 Springfox 迁移到 Springdoc OpenAPI 3 时,主要的工作是将原先使用的 Springfox 注解替换为 Springdoc OpenAPI 3 中的对应注解。虽然 Springdoc OpenAPI 3 基于 OpenAPI 3 规范,并且有一些不同的命名方式和设计理念,但大部分注解的…...

DIY-Tomcat part 3 实现对动态资源的请求
实现ServletRequest package connector;import javax.servlet.RequestDispatcher; import javax.servlet.ServletInputStream; import javax.servlet.ServletRequest; import java.io.BufferedReader; import java.io.IOException; import java.io.InputStream; import java.i…...
3.10 内核 BUG_ON() at xfs_vm_writepage() -> page_buffers()
目录 前言 问题分析 page buffers创建 page buffers丢失 Write-Protect Dirty Page w/o Buffers 问题解决 前言 这个问题发生在3.10.0-514.el7上,并且在RHEL的知识库中快速找到了对应的案例以及解决方案,但是,理解问题如何发生和解决…...

CrystalDiskInfo:硬盘健康监测工具简介和下载
原论坛给你更好的阅读体验:CrystalDiskInfo:硬盘健康监测工具简介和下载 | 波波论坛 引言 在日常使用电脑时,硬盘的健康状态对于系统的稳定性和数据的安全性至关重要。硬盘出现故障可能会导致数据丢失,严重时甚至会使整个系统无…...

eNSP-Cloud(实现本地电脑与eNSP内设备之间通信)
说明: 想象一下,你正在用eNSP搭建一个虚拟的网络世界,里面有虚拟的路由器、交换机、电脑(PC)等等。这些设备都在你的电脑里面“运行”,它们之间可以互相通信,就像一个封闭的小王国。 但是&#…...
vscode里如何用git
打开vs终端执行如下: 1 初始化 Git 仓库(如果尚未初始化) git init 2 添加文件到 Git 仓库 git add . 3 使用 git commit 命令来提交你的更改。确保在提交时加上一个有用的消息。 git commit -m "备注信息" 4 …...
<6>-MySQL表的增删查改
目录 一,create(创建表) 二,retrieve(查询表) 1,select列 2,where条件 三,update(更新表) 四,delete(删除表…...
进程地址空间(比特课总结)
一、进程地址空间 1. 环境变量 1 )⽤户级环境变量与系统级环境变量 全局属性:环境变量具有全局属性,会被⼦进程继承。例如当bash启动⼦进程时,环 境变量会⾃动传递给⼦进程。 本地变量限制:本地变量只在当前进程(ba…...

如何在看板中体现优先级变化
在看板中有效体现优先级变化的关键措施包括:采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中,设置任务排序规则尤其重要,因为它让看板视觉上直观地体…...

【分享】推荐一些办公小工具
1、PDF 在线转换 https://smallpdf.com/cn/pdf-tools 推荐理由:大部分的转换软件需要收费,要么功能不齐全,而开会员又用不了几次浪费钱,借用别人的又不安全。 这个网站它不需要登录或下载安装。而且提供的免费功能就能满足日常…...
A2A JS SDK 完整教程:快速入门指南
目录 什么是 A2A JS SDK?A2A JS 安装与设置A2A JS 核心概念创建你的第一个 A2A JS 代理A2A JS 服务端开发A2A JS 客户端使用A2A JS 高级特性A2A JS 最佳实践A2A JS 故障排除 什么是 A2A JS SDK? A2A JS SDK 是一个专为 JavaScript/TypeScript 开发者设计的强大库ÿ…...
NPOI操作EXCEL文件 ——CAD C# 二次开发
缺点:dll.版本容易加载错误。CAD加载插件时,没有加载所有类库。插件运行过程中用到某个类库,会从CAD的安装目录找,找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库,就用插件程序加载进…...

脑机新手指南(七):OpenBCI_GUI:从环境搭建到数据可视化(上)
一、OpenBCI_GUI 项目概述 (一)项目背景与目标 OpenBCI 是一个开源的脑电信号采集硬件平台,其配套的 OpenBCI_GUI 则是专为该硬件设计的图形化界面工具。对于研究人员、开发者和学生而言,首次接触 OpenBCI 设备时,往…...

pikachu靶场通关笔记19 SQL注入02-字符型注入(GET)
目录 一、SQL注入 二、字符型SQL注入 三、字符型注入与数字型注入 四、源码分析 五、渗透实战 1、渗透准备 2、SQL注入探测 (1)输入单引号 (2)万能注入语句 3、获取回显列orderby 4、获取数据库名database 5、获取表名…...