考研算法32天:桶排 【桶排序】

算法介绍

桶排

举个例子,一个数组中的数是:4 1 2 3 5,

然后桶排的顺序是:将每个数应该在的下标算出来,咋算呢?这我们就得考虑两种情况:假设我们设现在这个需要找到自己在数组里位置的数是x。

1.比x小的数有多少个

2.和x一样大并且原先就排在自己前面的数有多少个。

如果只考虑第一种情况很简单,但是如果两种情况都考虑呢?

那么我们就需要其他的东西来保证第二个相等的元素不改变位置了。那么这个东西是啥呢?很简单,一个前缀和:如何操作呢?还是举个例子:比如一个数列:3 2 2 1 5。我们求出其前缀和(这里的前缀和是其数字出现的个数的叠加并不是数的叠加),如下图

然后我们从后往前开始,(又因为其数列的数如果自己是x(n-1)那么自己的位置一定是x(n)-1)所以我们每个数的位置就是在其后面那个数的前面,因为我们序列最大的数是5所以从5开始我们发现其s5(序列和)=5并且数组中有这个数所以它应该放在下标为5的位置,然后向前遍历,1应该放在s1的位置=1,所以放在最开始的位置。以此类推。

算法题目

#include <iostream>

using namespace std;

const int N = 1000010;
int q[N], w[N];
int s[N];
void bucket_sort(int n){
    for(int i=0;i<n;i++){
        s[q[i]]++; 
    }
    for(int i=1;i<N;i++){
        s[i] = s[i-1] + s[i];
    }
    for(int i=n-1;i>=0;i--){
        w[--s[q[i]]] = q[i]; 
    }
    for(int i=0;i<n;i++){
        q[i] = w[i];
    }
    return;
}
int main(){
    int n;
    cin>>n;
    for(int i=0;i<n;i++)scanf("%d",&q[i]);
    bucket_sort(n);
    for(int i=0;i<n;i++)printf("%d ",q[i]);
    return 0;
}

acwing上面这段代码可以过10个数据。

算法复杂度

空间复杂度:O(n + m)

时间复杂度:O(n + m)

稳定性:稳定

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

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

【计算机网络】IP 地址处理函数

目录 1.struct sockaddr_in的结构 2.一般我们写的结构 3.常见的“点分十进制” 到 ” uint32_t 的转化接口 3.1. inet_aton 和 inet_ntoa &#xff08;ipv4&#xff09; 3.2. inet_pton 和 inet_ntop (ipv4 和 ipv6&#xff09; 3.3. inet_addr 和 inet_network 3…

哈工大计算机网络课程传输层协议之:拥塞控制原理剖析

哈工大计算机网络课程传输层协议之&#xff1a;拥塞控制原理剖析 哈工大计算机网络课程传输层协议详解之&#xff1a;可靠数据传输的基本原理 哈工大计算机网络课程传输层协议详解之&#xff1a;流水线机制与滑动窗口协议 哈工大计算机网络课程传输层协议详解之&#xff1a;T…

【裸机开发】EPIT 定时器 —— 按键消抖

实际工程中&#xff0c;不能直接通过延时来消抖 ! 这里我们采用定时器来消抖&#xff0c;这也是内核处理消抖的一种方式。 目录 一、基本原理 1、延时消抖的弊端 2、定时器消抖原理 二、按键消抖实现 1、按键中断 2、定时器中断 三、附加&#xff1a;按键 / 定时器中断初…

Qgis加载在线XYZ瓦片影像服务的实践操作

目录 背景 一、XYZ瓦片相关知识 1、xyz瓦片金字塔 2、 瓦片编号 3、瓦片访问 二、在Qgis中加载在线地图 1、Qgis版本 2、瓦片加载 3、地图属性预览 总结 背景 在做电子地图应用的时候&#xff0c;很常见的会提到瓦片&#xff08;tile&#xff09;的概念&#xff0c;瓦片…

【MySQL】MVCC是如何解决快照读下的幻读问题的

文章目录 LBCC当前读 MVCC隐藏列undo logRead View 总结 我们从上文中了解到InnoDB默认的事务隔离级别是repeatable read&#xff08;后文中用简称RR&#xff09;&#xff0c;它为了解决该隔离级别下的幻读的并发问题&#xff0c;提出了LBCC和MVCC两种方案。其中LBCC解决的是当…

信号链噪声分析11

文章目录 概要整体架构流程技术名词解释技术细节小结 概要 提示&#xff1a;这里可以添加技术概要 如今的射频(RF)系统变得越来越复杂。高度的复杂性要求所有系统指标&#xff08;例如严格的 链接和噪声预算&#xff09;达到最佳性能。确保整个信号链的正确设计至关重要。而信…

如何了解(海外抖音TiKToK)与国内抖音的区别以及介绍

一、海外抖音TK平台的优势 自从抖音在中国大受欢迎后&#xff0c;海外也推出了海外版抖音TK平台。尽管两者都是视频分享平台&#xff0c;但它们在一些方面具有明显的区别和独特的优势。下面将详细介绍海外抖音TK平台的优势以及与国内抖音的区别性。 优势&#xff1a; 1. 多元…

三防工业平板在哪些行业中得到广泛应用?

随着科技的不断进步&#xff0c;工业平板正逐渐成为各行业中不可或缺的工具。其中&#xff0c;三防工业平板由于其卓越的耐用性和丰富的功能&#xff0c;在许多行业中得到了广泛的应用。本文将重点介绍三防工业平板在以下几个行业中的应用。 三防工业平板在物流行业中发挥着关键…

vue-router.esm.js:2248 Error: Cannot find module ‘@/views/dylife/ 报错解决

具体是展示 一直加载 控制台报找不到模块 webpack版本问题&#xff0c;webpack4 不支持变量方式的动态 import &#xff0c;新版本需要使用 require() 来解决此问题。 return () > import(/views/${view}) 改写成 return (resolve) > require([/views/${view}], reso…

【三层交换机】网络杂谈(16)之三层交换机技术

涉及知识点 什么是三层交换机&#xff0c;三层交换技术的由来&#xff0c;三层交换机&#xff0c;三层交换的应用范例。深入了解三层交换机技术。 原创于&#xff1a;CSDN博主-《拄杖盲学轻声码》&#xff0c;更多内容可去其主页关注下哈&#xff0c;不胜感激 文章目录 涉及知…

HBase(5):导入测试数据集

1 需求 将ORDER_INFO.txt 中的HBase数据集&#xff0c;我们需要将这些指令放到HBase中执行&#xff0c;将数据导入到HBase中。 可以看到这些都是一堆的put语句。那么如何才能将这些语句全部执行呢&#xff1f; 2 执行command文件 2.1 上传command文件 将该数据集文件上传到指…

6.5 指令与文件的搜寻

6.5.1 指令文件名的搜寻 在终端机模式当中&#xff0c;连续输入两次[tab]按键就能够知道使用者有多少指令可以下达。 which &#xff08;寻找“可执行文件”&#xff09; 这个指令是根据“PATH”这个环境变量所规范的路径&#xff0c;去搜寻“可执行文件”的文件名。所以&…

DETR系列:RT-DETR(一) 论文解析

论文&#xff1a;《DETRs Beat YOLOs on Real-time Object Detection》 2023.4 DETRs Beat YOLOs on Real-time Object Detection&#xff1a;https://arxiv.org/pdf/2304.08069.pdf 源码地址&#xff1a;https://github.com/PaddlePaddle/PaddleDetection/tree/develop/conf…

【Visual Studio】报错 ASSERT: “i >= 0 i < size()“,使用 C++ 语言,配合 Qt 开发串口通信界面

知识不是单独的&#xff0c;一定是成体系的。更多我的个人总结和相关经验可查阅这个专栏&#xff1a;Visual Studio。 这个 Bug 是我做这个工程时遇到的&#xff1a;【Visual Studio】Qt 的实时绘图曲线功能&#xff0c;使用 C 语言&#xff0c;配合 Qt 开发串口通信界面。 文…

javaweb学习2

p标签使用 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Title</title> </head> <body> <!--p标签定义段落 p元素自动在其前后创建一段空白--> hello&#xff0c;world &l…

设计模式之访问者模式笔记

设计模式之访问者模式笔记 说明Iterator(访问者)目录访问者模式示例类图抽象访问者角色类抽象元素角色类宠物猫类宠物狗类自己类其他人类家类测试类 说明 记录下学习设计模式-访问者模式的写法。JDK使用版本为1.8版本。 Iterator(访问者) 意图:表示一个作用于某对象结构中的…

日历组件 el-calendar 实现标记功能

需求&#xff1a;在日历组件中选择月份时&#xff0c;可以显示当月已经质检或需质检的数据 思路&#xff1a;前端每次点击日期选择器的时候调用接口&#xff0c;接口返回当月需要质检或已质检的数据&#xff0c;前端拿到数据就开始做判断然后回显。 大体样式 代码&#xff1a…

Redis7【① 概述 安装 配置】

1. Redis入门概述 1. Redis是什么 Redis全称 远程字典服务器&#xff08;Remote Dictionary Server&#xff09;&#xff0c;它是完全开源的&#xff0c;使用ANSIC语言编写遵守BSD协议&#xff0c;是一个高性能的基于内存的Key-Value数据库&#xff0c;提供了丰富的数据结构&…

windows无法启动RemoteDesktopServices服务(位于本地计算机上)。错误126:找不到指定的模块。

win10的搜索栏输入 注册表编辑器。打开&#xff0c;找到如下路径 计算机\HKEY_LOCAL_MACHINE\SYSTEM\CurrentControlSet\Services\TermService\Parameters 将指定数值项ServiceDll的数值数据改成默认值&#xff1a; %SystemRoot%\System32\termsrv.dll 再重新尝试就好了。 …

Spring是什么?

目录 1、Spring的简介 2、Spring七大功能模块 3、Spring的优点 4、Spring的缺点 5、Sprig容器 6、Spring的生态圈&#xff08;重点&#xff09;***** 7、Spring中bean的生命周期 1、Spring的简介 Spring的英文翻译为春天&#xff0c;可以说是给Java程序员带来了春天&…