当前位置: 首页 > news >正文

c++ 桶排序(看这一篇就够了)

1. 概述

桶排序(Bucket Sort)又称箱排序,是一种比较常用的排序算法。其算法原理是将数组分到有限数量的桶里,再对每个桶分别排好序(可以是递归使用桶排序,也可以是使用其他排序算法将每个桶分别排好序),最后一次将每个桶中排好序的数输出。

2. 算法详解

桶排序的思想就是把待排序的数尽量均匀地放到各个桶中,再对各个桶进行局部的排序,最后再按序将各个桶中的数输出,即可得到排好序的数。

    首先确定桶的个数。因为桶排序最好是将数据均匀地分散在各个桶中,那么桶的个数最好是应该根据数据的分散情况来确定。首先找出所有数据中的最大值mx和最小值mn;

    根据mx和mn确定每个桶所装的数据的范围 size,有
    size = (mx - mn) / n + 1,n为数据的个数,需要保证至少有一个桶,故而需要加个1;

    求得了size即知道了每个桶所装数据的范围,还需要计算出所需的桶的个数cnt,有
    cnt = (mx - mn) / size + 1,需要保证每个桶至少要能装1个数,故而需要加个1;

    求得了size和cnt后,即可知第一个桶装的数据范围为 [mn, mn + size),第二个桶为 [mn + size, mn + 2 * size),…,以此类推
    因此步骤2中需要再扫描一遍数组,将待排序的各个数放进对应的桶中。

    对各个桶中的数据进行排序,可以使用其他的排序算法排序,例如快速排序;也可以递归使用桶排序进行排序;

    将各个桶中排好序的数据依次输出,最后得到的数据即为最终有序。

例子:待排序的数为:3, 6, 9, 1

1)求得 mx = 9,mn = 1,n = 4
size = (9 - 1) / n + 1 = 3
cnt = (mx - mn) / size + 1 = 3

2)由上面的步骤可知,共3个桶,每个桶能放3个数,第一个桶数的范围为 [1, 4),第二个[4, 7),第三个[7, 10)
扫描一遍待排序的数,将各个数放到其对应的桶中,放完后如下图所示:

3)对各个桶中的数进行排序,得到如下图所示:

4)依次输出各个排好序的桶中的数据,即为:1, 3, 6, 9
可见,最终得到了有序的排列。

3. 时间复杂度和空间复杂度分析

最好时间复杂度 : O(n + k)
其中k为桶的个数。即当数据是均匀分散排列的,那么每个桶分到的数据个数都是一样的,这个步骤需要O(k)的书剑复杂度,在对每个桶进行排序的时候,最好情况下是数据都已经是有序的了,那么最好的排序算法的时间复杂度会是O(n),因此总的时间复杂度是 O(n + k) 。

最坏时间复杂度:O(n^2)
当对每个桶中的数据进行排序的时候,所使用的排序算法,最坏情况下是O(n^2),因此总的最坏情况下的时间复杂度为O(n^2)。

平均时间复杂度:O(n + n²/k + k) <=> O(n)
如果k是根据Θ(n)来获取的,那么平均时间复杂度就是 O(n)。

 4.桶排序误区

1、如果数据分布不均,大量数据集中在少量桶里,桶排序就没有效果。

2、桶排序要时间就省不了空间,要空间就省不了时间,意义不大。

首先桶排序排序的内容是均匀分布的一串数字,不存在数据分布不均的问题。其次桶排序可以在时间和空间之间找一个点,使其满足两者。

5.代码

#include <stdio.h>
#include <stdlib.h>// 桶排序函数
void bucketSort(int arr[], int n) {// 创建桶数组int maxVal = arr[0];for (int i = 1; i < n; i++) {if (arr[i] > maxVal) {maxVal = arr[i];}}int bucket[maxVal + 1];for (int i = 0; i <= maxVal; i++) {bucket[i] = 0;}// 将元素放入桶中for (int i = 0; i < n; i++) {bucket[arr[i]]++;}// 从桶中取出元素并排序int index = 0;for (int i = 0; i <= maxVal; i++) {while (bucket[i] > 0) {arr[index++] = i;bucket[i]--;}}
}// 测试桶排序
int main() {int arr[] = {5, 2, 8, 4, 9, 1, 3, 7, 6};int n = sizeof(arr) / sizeof(arr[0]);printf("原始数组:");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");bucketSort(arr, n);printf("排序后数组:");for (int i = 0; i < n; i++) {printf("%d ", arr[i]);}printf("\n");return 0;
}
参考文章:桶排序详解-CSDN博客文章浏览阅读2.9k次,点赞19次,收藏30次。本文详细介绍了桶排序的基本原理,如何利用哈希表进行数据分配,以及进阶方法中如何通过区间划分和链表结构进行排序。特别强调了桶排序对数据分布均匀性的依赖和在时间和空间效率上的平衡。https://blog.csdn.net/2302_80297670/article/details/135852102?ops_request_misc=%257B%2522request%255Fid%2522%253A%25226BEB34D7-B27C-41C3-9542-2CA003EEF8BE%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=6BEB34D7-B27C-41C3-9542-2CA003EEF8BE&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-2-135852102-null-null.142^v100^pc_search_result_base6&utm_term=%E6%A1%B6%E6%8E%92%E5%BA%8F&spm=1018.2226.3001.4187
【算法】桶排序(Bucket Sort)详解-CSDN博客文章浏览阅读2.8w次,点赞56次,收藏351次。桶排序_桶排序https://blog.csdn.net/qq_27198345/article/details/126516234?ops_request_misc=%257B%2522request%255Fid%2522%253A%25226BEB34D7-B27C-41C3-9542-2CA003EEF8BE%2522%252C%2522scm%2522%253A%252220140713.130102334..%2522%257D&request_id=6BEB34D7-B27C-41C3-9542-2CA003EEF8BE&biz_id=0&utm_medium=distribute.pc_search_result.none-task-blog-2~all~top_positive~default-1-126516234-null-null.142^v100^pc_search_result_base6&utm_term=%E6%A1%B6%E6%8E%92%E5%BA%8F

                
 

相关文章:

c++ 桶排序(看这一篇就够了)

1. 概述 桶排序&#xff08;Bucket Sort&#xff09;又称箱排序&#xff0c;是一种比较常用的排序算法。其算法原理是将数组分到有限数量的桶里&#xff0c;再对每个桶分别排好序&#xff08;可以是递归使用桶排序&#xff0c;也可以是使用其他排序算法将每个桶分别排好序&…...

格点拉格朗日插值与PME算法

技术背景 在前面的一篇博客中&#xff0c;我们介绍了拉格朗日插值法的基本由来和表示形式。这里我们要介绍一种拉格朗日插值法的应用场景&#xff1a;格点拉格朗日插值法。这种场景的优势在于&#xff0c;如果我们要对整个实数空间进行求和或者积分&#xff0c;计算量是随着变量…...

【LVGL快速入门(二)】LVGL开源框架入门教程之框架使用(UI界面设计)

零.前置篇章 本篇前置文章为【LVGL快速入门(一)】LVGL开源框架入门教程之框架移植 一.UI设计 介绍使用之前&#xff0c;我们要学习一款LVGL官方的UI设计工具SquareLine Studio&#xff0c;使用图形化设计方式设计出我们想要的界面&#xff0c;然后生成对应源文件导入工程使用…...

jmeter中用csv data set config做参数化2

在jmeter中&#xff0c;使用csv data set config进行参数化是很重要的一个功能&#xff0c;但是这个功能的使用需要十分仔细和小心&#xff0c;因为细节之处往往决定着结果的正确与否。 举例&#xff1a; 一个登录接口用加密密码登录&#xff0c;一个登录接口用原始密码登录。…...

背包问题整理

1.01背包 题目描述 小明有一个容量为 V 的背包。 这天他去商场购物&#xff0c;商场一共有N 件物品&#xff0c;第 i 件物品的体积为 wi&#xff0c;价值为 vi。 小明想知道在购买的物品总体积不超过 V的情况下所能获得的最大价值为多少&#xff0c;请你帮他算算。 输入描述…...

基于Matlab车牌识别课程设计报告

Matlab车牌识别系统 分院&#xff08;系&#xff09; 信息科学与工程 专业 学生姓名 学号 设计题目 车牌识别系统设计 内容及要求&#xff1a; 车牌定位系统的目的在于正确获取整个图像中车牌的区域&#xff0c; 并识别出车牌号。通过设计实现车牌识别系…...

SSM框架实战小项目:打造高效用户管理系统 day3

前言 在前两篇博客中&#xff0c;后台已经搭建完毕&#xff0c;现在需要设计一下前端页面 webapp下的项目结构图 创建ftl文件夹&#xff0c;导入css和js 因为我们在后台的视图解析器中&#xff0c;设置了页面解析器&#xff0c;跳转路径为/ftl/*.ftl&#xff0c;所以需要ftl文件…...

一款现代化、可定制的跨平台文件浏览器,高颜值高效率的的管理神器!(附私活源码)

在如今这个注重效率的时代&#xff0c;我们每天都在与文件打交道。 但是&#xff0c;你有没有感觉到传统的文件管理器总是让人提不起劲&#xff1f;单调的外观&#xff0c;有限的功能&#xff0c;仿佛是上个世纪的产物。 一直以来&#xff0c;我都在寻找一款既颜值高又功能强…...

【C】二分查找与函数1

二分查找 练习&#xff1a; 给定一个整型的有序数组&#xff0c;在数组中找到指定的一个值&#xff0c;如&#xff1a; 1&#xff0c;2&#xff0c;3&#xff0c;4&#xff0c;5&#xff0c;6&#xff0c;7&#xff0c;8&#xff0c;9&#xff0c;10 找出7.如果找到了&#x…...

光纤光学的基本方程

一、麦克斯韦方程与亥姆赫兹方程 1.1 麦克斯韦方程 光纤是一种介质光波导&#xff0c;具有以下特点&#xff1a; ① 无传导电流 ② 无自由电荷 ③ 线性各向同性 推导出来的即为波动方程。为材料在真空中的磁导率&#xff0c;为材料在真空中的介电常数&#xff0c;n为材料折…...

题解:CF584D Dima and Lisa

前置知识 哥德巴赫猜想&#xff0c;任一大于 2 2 2 的偶数都可写成两个素数之和。 思路 我们可以分类讨论一下。 n n n 一开始就是质数。直接输出即可 n n n 是偶数&#xff0c;那么一定可以写成两个质数之和。那么暴力枚举两个质数即可。 如果以上均不符合&#xff0c;计…...

【OD】【E卷】【真题】【100分】内存资源分配(PythonJavaJavaScriptC++C)

题目描述 有一个简易内存池&#xff0c;内存按照大小粒度分类&#xff0c;每个粒度有若干个可用内存资源&#xff0c;用户会进行一系列内存申请&#xff0c;需要按需分配内存池中的资源返回申请结果成功失败列表。 分配规则如下&#xff1a; 分配的内存要大于等于内存的申请…...

Linux基础项目开发day05:量产工具——页面系统

文章目录 一、数据结构抽象page_manager.h 二、页面管理器page_manager.c 三、单元测试1、main.page.c2、page_test.c3、Makefile修改3.1、unittest中的Makefile3.2、page中的Makefile 四、上机实验 前言 前面实现了显示、输入、文字、UI系统&#xff0c;现在我们就来实现页面的…...

保护企业终端安全,天锐DLP帮助企业智能管控终端资产

为有效预防员工非法调包公司的软硬件终端资产&#xff0c;企业管理员必须建立高效的企业终端安全管控机制&#xff0c;确保能够即时洞察并确认公司所有软硬件资产的状态变化。这要求企业要有一套能够全面管理终端资产的管理系统&#xff0c;确保任何未经授权的资产变动都能被迅…...

2024市场营销第3次课

品牌管理 1.认识品牌 品牌定义&#xff1a;一个名称、术语、标志、符号或设计&#xff0c;或者是它们的组合&#xff0c;用来识别某个销售商或某一群销售商的产品或服务&#xff0c;并使其与竞争者的产品或服务区分开来。 品牌构成&#xff1a;成功品牌的构成都是由外及内的…...

Python基础之函数的定义与调用

一、函数的定义 在Python中&#xff0c;函数是一段可重复使用的代码块&#xff0c;用于完成特定的任务。可以使用def关键字来定义函数。 语法如下&#xff1a; def function_name(parameters): """docstring""" # function body return expres…...

GPU在AI绘画中的作用以及GPU的选择

大家好&#xff0c;我是Shelly&#xff0c;一个专注于输出AI工具和科技前沿内容的AI应用教练&#xff0c;体验过300款以上的AI应用工具。关注科技及大模型领域对社会的影响10年。关注我一起驾驭AI工具&#xff0c;拥抱AI时代的到来。 GPU在AI绘画中的作用&#xff1a; GPU在A…...

【火山引擎】 Chat实践 | 大模型调用实践 | python

目录 一 前期工作 二 Doubao-pro-4k_test实践 一 前期工作 1 已在火山方舟控制台在线推理页面创建了推理接入点 ,接入大语言模型并获取接入点 ID。 2 已参考安装与初始化中的步骤完成 SDK 安装和访问凭证配置...

mysql学习教程,从入门到精通,SQL 注入(42)

1、 SQL 注入 SQL 注入是一种严重的安全漏洞&#xff0c;它允许攻击者通过操纵 SQL 查询来访问、修改或删除数据库中的数据。由于 SQL 注入的潜在危害&#xff0c;我不能提供具体的恶意代码示例。然而&#xff0c;我可以向你展示如何防御 SQL 注入&#xff0c;并解释其工作原理…...

图论day60|108.冗余连接(卡码网) 、109.冗余连接II(卡码网)【并查集 摧毁信心的一题,胆小的走开!】

图论day60|108.冗余连接&#xff08;卡码网&#xff09;、109.冗余连接II&#xff08;卡码网&#xff09;【并查集 摧毁信心的一题&#xff0c;胆小的走开&#xff01;】 108.冗余连接&#xff08;卡码网&#xff09;109.冗余连接II&#xff08;卡码网&#xff09;【并查集 摧毁…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

macOS多出来了:Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用

文章目录 问题现象问题原因解决办法 问题现象 macOS启动台&#xff08;Launchpad&#xff09;多出来了&#xff1a;Google云端硬盘、YouTube、表格、幻灯片、Gmail、Google文档等应用。 问题原因 很明显&#xff0c;都是Google家的办公全家桶。这些应用并不是通过独立安装的…...

DIY|Mac 搭建 ESP-IDF 开发环境及编译小智 AI

前一阵子在百度 AI 开发者大会上&#xff0c;看到基于小智 AI DIY 玩具的演示&#xff0c;感觉有点意思&#xff0c;想着自己也来试试。 如果只是想烧录现成的固件&#xff0c;乐鑫官方除了提供了 Windows 版本的 Flash 下载工具 之外&#xff0c;还提供了基于网页版的 ESP LA…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

C++八股 —— 单例模式

文章目录 1. 基本概念2. 设计要点3. 实现方式4. 详解懒汉模式 1. 基本概念 线程安全&#xff08;Thread Safety&#xff09; 线程安全是指在多线程环境下&#xff0c;某个函数、类或代码片段能够被多个线程同时调用时&#xff0c;仍能保证数据的一致性和逻辑的正确性&#xf…...

LINUX 69 FTP 客服管理系统 man 5 /etc/vsftpd/vsftpd.conf

FTP 客服管理系统 实现kefu123登录&#xff0c;不允许匿名访问&#xff0c;kefu只能访问/data/kefu目录&#xff0c;不能查看其他目录 创建账号密码 useradd kefu echo 123|passwd -stdin kefu [rootcode caozx26420]# echo 123|passwd --stdin kefu 更改用户 kefu 的密码…...

使用Spring AI和MCP协议构建图片搜索服务

目录 使用Spring AI和MCP协议构建图片搜索服务 引言 技术栈概览 项目架构设计 架构图 服务端开发 1. 创建Spring Boot项目 2. 实现图片搜索工具 3. 配置传输模式 Stdio模式&#xff08;本地调用&#xff09; SSE模式&#xff08;远程调用&#xff09; 4. 注册工具提…...

GruntJS-前端自动化任务运行器从入门到实战

Grunt 完全指南&#xff1a;从入门到实战 一、Grunt 是什么&#xff1f; Grunt是一个基于 Node.js 的前端自动化任务运行器&#xff0c;主要用于自动化执行项目开发中重复性高的任务&#xff0c;例如文件压缩、代码编译、语法检查、单元测试、文件合并等。通过配置简洁的任务…...

Redis:现代应用开发的高效内存数据存储利器

一、Redis的起源与发展 Redis最初由意大利程序员Salvatore Sanfilippo在2009年开发&#xff0c;其初衷是为了满足他自己的一个项目需求&#xff0c;即需要一个高性能的键值存储系统来解决传统数据库在高并发场景下的性能瓶颈。随着项目的开源&#xff0c;Redis凭借其简单易用、…...

比较数据迁移后MySQL数据库和OceanBase数据仓库中的表

设计一个MySQL数据库和OceanBase数据仓库的表数据比较的详细程序流程,两张表是相同的结构,都有整型主键id字段,需要每次从数据库分批取得2000条数据,用于比较,比较操作的同时可以再取2000条数据,等上一次比较完成之后,开始比较,直到比较完所有的数据。比较操作需要比较…...