当前位置: 首页 > 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;【并查集 摧毁…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

ES6从入门到精通:前言

ES6简介 ES6&#xff08;ECMAScript 2015&#xff09;是JavaScript语言的重大更新&#xff0c;引入了许多新特性&#xff0c;包括语法糖、新数据类型、模块化支持等&#xff0c;显著提升了开发效率和代码可维护性。 核心知识点概览 变量声明 let 和 const 取代 var&#xf…...

相机从app启动流程

一、流程框架图 二、具体流程分析 1、得到cameralist和对应的静态信息 目录如下: 重点代码分析: 启动相机前,先要通过getCameraIdList获取camera的个数以及id,然后可以通过getCameraCharacteristics获取对应id camera的capabilities(静态信息)进行一些openCamera前的…...

ServerTrust 并非唯一

NSURLAuthenticationMethodServerTrust 只是 authenticationMethod 的冰山一角 要理解 NSURLAuthenticationMethodServerTrust, 首先要明白它只是 authenticationMethod 的选项之一, 并非唯一 1 先厘清概念 点说明authenticationMethodURLAuthenticationChallenge.protectionS…...

是否存在路径(FIFOBB算法)

题目描述 一个具有 n 个顶点e条边的无向图&#xff0c;该图顶点的编号依次为0到n-1且不存在顶点与自身相连的边。请使用FIFOBB算法编写程序&#xff0c;确定是否存在从顶点 source到顶点 destination的路径。 输入 第一行两个整数&#xff0c;分别表示n 和 e 的值&#xff08;1…...

人工智能(大型语言模型 LLMs)对不同学科的影响以及由此产生的新学习方式

今天是关于AI如何在教学中增强学生的学习体验&#xff0c;我把重要信息标红了。人文学科的价值被低估了 ⬇️ 转型与必要性 人工智能正在深刻地改变教育&#xff0c;这并非炒作&#xff0c;而是已经发生的巨大变革。教育机构和教育者不能忽视它&#xff0c;试图简单地禁止学生使…...

搭建DNS域名解析服务器(正向解析资源文件)

正向解析资源文件 1&#xff09;准备工作 服务端及客户端都关闭安全软件 [rootlocalhost ~]# systemctl stop firewalld [rootlocalhost ~]# setenforce 0 2&#xff09;服务端安装软件&#xff1a;bind 1.配置yum源 [rootlocalhost ~]# cat /etc/yum.repos.d/base.repo [Base…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

消息队列系统设计与实践全解析

文章目录 &#x1f680; 消息队列系统设计与实践全解析&#x1f50d; 一、消息队列选型1.1 业务场景匹配矩阵1.2 吞吐量/延迟/可靠性权衡&#x1f4a1; 权衡决策框架 1.3 运维复杂度评估&#x1f527; 运维成本降低策略 &#x1f3d7;️ 二、典型架构设计2.1 分布式事务最终一致…...

python读取SQLite表个并生成pdf文件

代码用于创建含50列的SQLite数据库并插入500行随机浮点数据&#xff0c;随后读取数据&#xff0c;通过ReportLab生成横向PDF表格&#xff0c;包含格式化&#xff08;两位小数&#xff09;及表头、网格线等美观样式。 # 导入所需库 import sqlite3 # 用于操作…...