排序算法:n个0~1000之间的整数,将他们从大到小排序

上榜理由:

        如果没见过这种排序题,可能首先想到的就是常用的排序算法,比如快速排序,归并排序,那如果输入的n足够大,时间复杂度肯定比较高。其实题目0-1000的范围是一个题眼,所以一定有更优的排序算法:这里用到了桶排序!

回顾经典排序算法有

  • 冒泡排序(Bubble Sort)
  • 插入排序(Insertion Sort)
  • 希尔排序(Shell Sort)
  • 选择排序(Selection Sort)
  • 快速排序(Quick Sort)
  • 归并排序(Merge Sort)
  • 堆排序(Heap Sort)
  • 计数排序(Counting Sort)
  • 桶排序(Bucket Sort)

思路就是:

首先,0-1000的值域,创建1001个桶,每个桶都对应一个index,里面放一个初始值count=0,表示大小是index的数出现的个数。

然后遍历n个数,就把这1001个桶里的count更新一次,

接着再根据要求从大到小,或者从下到大遍历1001个桶,如果count>0,表示出现过count,就打印count个对应桶index的值,

最后,就完成了排序算法输出!

    //bucket_sort.cpp
	
    #include <stdio.h>
	#include <cstring>
	int main()
	{
	    int bucket[1001],i,j,t,n;
	    memset(bucket,0,sizeof bucket);
	    printf("please enter total number = \n");
	    scanf("%d",&n);//输入一个数n,表示接下来有n个数
	    printf("now please enter the data\n");
	    for(i=1;i<=n;i++)//循环读入n个数,并进行桶排序
	    {
	        scanf("%d",&t);  //把每一个数读到变量t中
	        bucket[t]++;  //进行计数,对编号为t的桶放一个小旗子
	    }
	    printf("sort data is: \n");
	    for(i=1000;i>=0;i--)  //依次判断编号1000~0的桶
	        for(j=1;j<=bucket[i];j++)  //出现了几次就将桶的编号打印几次
	             printf("%d ",i);
	             
	    printf("\n");
	    return 0;
	}

附个编译代码和输出测试

gcc -o test bucket_sort.cpp

./test

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

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

相关文章

【鸿蒙应用ArkTS开发系列】- 选择图片、文件和拍照功能实现

文章目录 前言创建多媒体Demo工程创建MediaBean 实体类创建MediaHelper工具类API标记弃用问题动态申请多媒体访问权限实现选择图片显示功能打包测试 前言 在使用App的时候&#xff0c;我们经常会在一些社交软件中聊天时发一些图片或者文件之类的多媒体文件&#xff0c;那在鸿蒙…

网络安全--基于Kali的网络扫描基础技术

文章目录 1. 标准ICMP扫描1.1使用Ping命令1.1.1格式1.1.2实战 1.2使用Nmap工具1.2.1格式1.2.2实战1.2.2.1主机在线1.2.2.2主机不在线 1.3使用Fping命令1.3.1格式1.3.2实战 2. 时间戳查询扫描2.1格式2.2实战 3. 地址掩码查询扫描3.1格式3.2实战 2. TCP扫描2.1TCP工作机制2.2TCP …

拆解按摩器:有意思的按键与LED控制电路,学习借鉴一下!

拆解 外观和配色个人感觉还行,比较青春 拉开拉链&#xff0c;拆开外面的布面&#xff0c;里面还有一层纱面 按键部分使用魔术贴固定 拆开纱面后&#xff0c;看到里面的结构&#xff0c;整体是一个海绵 可以看到如下&#xff0c;电池&#xff0c;按键板&#xff0c;充电线的三条…

【Java】文件路径-绝对路径与相对路径

1、绝对路径与相对路径 先来看一下绝对路径和相对路径的定义&#xff1a; 绝对路径是指完整的描述文件位置的路径就是绝对路径。如Windows系统中的D:\Project\data\test.txt&#xff0c;MAC系统中的/Users/liuwenwen/Desktop/Project/test.txt 相对路径是指相对于当前文件位置…

[操作系统] 面试宝典之~死锁连环系列

文章目录 2.22 什么是死锁2.24 解决死锁的方法死锁的预防死锁的避免死锁的检测死锁的解除 2.22 什么是死锁 在多道程序环境下&#xff0c;多个进程可以竞争有限数量的资源。当一个进程申请资源时&#xff0c;如果这时没有可用资源&#xff0c;那么这个进程进入等待状态。有时&…

什么是高级语言、机器语言、汇编语言?什么是编译和解释?

1、高级语言 计算机程序是一种让计算机执行特定任务的方法。程序是由程序员用一种称为编程语言的特殊语言编写的。编程语言有很多种&#xff0c;例如 C、C、Java、Python 等。这些语言被称为高级语言&#xff0c;因为它们更接近人类的自然语言&#xff0c;而不是计算机能够直接…

【数据结构 —— 二叉树的链式结构实现】

数据结构 —— 二叉树的链式结构实现 1.树的概念及其结构1.1.树概念1.2.树的结构1.3树的相关概念1.4.树的表示1.5. 树在实际中的运用&#xff08;表示文件系统的目录树结构&#xff09; 2.二叉树的概念及其结构2.1二叉树的概念2.2.现实中的二叉树&#xff1a;2.3. 特殊的二叉树…

C++单调向量(栈):好子数组的最大分数

作者推荐 利用广度优先或模拟解决米诺骨牌 题目 给你一个整数数组 nums &#xff08;下标从 0 开始&#xff09;和一个整数 k 。 一个子数组 (i, j) 的 分数 定义为 min(nums[i], nums[i1], …, nums[j]) * (j - i 1) 。一个 好 子数组的两个端点下标需要满足 i < k <…

32+OLED之IIC手撕亚索七级狗牌

成品效果&#xff1a; 硬件配方&#xff1a;STM32F103C8T6 SSD1306 软件配方&#xff1a;字模提取V2.1 CopyLeft By Horse2000 STM32CubeMX keil5 思路&#xff1a; 1.找到图片&#xff0c;将其转化为128*64 像素大小的二值化图片&#xff1b;【python实现转化】&#xff…

配置zabbix-proxy主动式

IP地址对应关系如下&#xff1a; zabbix-server122.9.8.21zabbix-proxy122.9.4.102zabbix-agent2116.63.9.109 一、 安装zabbix-server https://blog.csdn.net/qq_50247813/article/details/132131774 二、 安装zabbix-proxy a. 安装zabbix源 rpm -Uvh https://repo.zabbix…

机器学习笔记 - 基于百度飞桨PaddleSeg的人体分割

一、简述 虽然Segment Anything用于图像分割的通用大模型看起来很酷(飞桨也提供分割一切的模型),但是个人感觉落地应用的时候心里还是更倾向于飞桨这种场景式的,因为需要用到一些人体分割的需求,所以这里主要是对飞桨高性能图像分割开发套件进行了解和使用,但是暂时不训练…

Modbus平台:协议中间件(支持Modbus TCP、RTU、ASCII)

该程序可放置外网中&#xff0c;适用于DTU长连接&#xff08;心跳包必须包含DTU&#xff0c;可以是tcp/udp&#xff09;&#xff0c;也可以在内网中&#xff0c;短连接访问设备server 支持协议&#xff1a;Modbus TCP | RTU | ASCII 连接方式&#xff1a;TcpAtive: TCP主动 | …

机器人制作开源方案 | 智能扶老助残辅助管家

作者&#xff1a;孙运通 黄善越 卢瑀 张宇峰 郑乐怡 单位&#xff1a;河海大学 指导老师&#xff1a;陆其清 人口老龄化始终是我国一个极为严峻的社会问题。独居老人和空巢老人占总人口比重日益提高&#xff1a;预计至2050年老龄人口占比将超20%&#xff0c;绝大部分城市和地…

基于单片机环境监测温湿度PM2.5系统设计

**单片机设计介绍&#xff0c;基于单片机环境监测温湿度PM2.5系统设计 文章目录 一 概要二、功能设计设计思路 三、 软件设计原理图 五、 程序六、 文章目录 一 概要 设计一个基于单片机环境监测温湿度PM2.5的系统是一个非常有意义的项目。以下是一个基本的介绍&#xff1a; …

云原生实战课大纲<2>

我们pod的数据挂载文件可以使用 pv-pvc的方式 1. 创建pv池 2. 在pv池中创建pv&#xff0c;并且设置pv的模式 3. 编写pod 写对应的pvc 申请书 就可以了这就是我们k8s中的pv和pvc 基于pv池创建pv的时候会有容量限制呢么关于配置呢&#xff0c;我们以前会有这种场景 比如说在dock…

Android Studio导入项目一直显示正在下载Gradle项目

如题&#xff0c;问题图类似如下&#xff1a; &#xff08;此图是解决以后截的&#xff0c;之前遇到问题没截图&#xff09; 解决方法 先找到你正在下载的gradle的版本是哪个 然后在链接中 ​​​​​​Gradle Distributions 找到你所对于gradle的版本&#xff0c;下载对应…

Centos7安装配置nginx

快捷查看指令 ctrlf 进行搜索会直接定位到需要的知识点和命令讲解&#xff08;如有不正确的地方欢迎各位小伙伴在评论区提意见&#xff0c;小编会及时修改&#xff09; Centos7安装配置nginx Nginx介绍 Nginx (engine x) 是一个高性能的 HTTP 和 反向代理 服务&#xff0c;也…

Spring Security 6.x 系列(6)—— 显式设置和修改登录态信息

一、前言 此篇是对上篇 Spring Security 6.x 系列&#xff08;5&#xff09;—— Servlet 认证体系结构介绍 中4.9章节显式调用SecurityContextRepository#saveContext进行详解分析。 二、设置和修改登录态 2.1 登录态存储形式 使用Spring Security框架&#xff0c;认证成功…

34 - 记一次线上SQL死锁事故:如何避免死锁?

之前我参与过一个项目&#xff0c;在项目初期&#xff0c;我们是没有将读写表分离的&#xff0c;而是基于一个主库完成读写操作。在业务量逐渐增大的时候&#xff0c;我们偶尔会收到系统的异常报警信息&#xff0c;DBA 通知我们数据库出现了死锁异常。 按理说业务开始是比较简…

业务逻辑漏洞

业务逻辑漏洞 扫描器扫不出来 漏洞包括 暴力破解任意用户/密码登陆短信/邮箱轰炸验证码绕过/爆破/重放/回传用户名/手机号枚举(用户名枚举&#xff1a;当用户登录时&#xff0c;显示用户名不存在&#xff0c;或密码不正确&#xff0c;两个其中一个不正确就称为用户名枚举)越…