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

深入了解桶排序:原理、性能分析与 Java 实现

桶排序(Bucket Sort)是一种排序算法,通常用于将一组数据分割成有限数量的桶(或容器),然后对每个桶中的数据进行排序,最后将这些桶按顺序合并以得到排好序的数据集。

buckersort.jpg

桶排序原理

  1. 确定桶的数量:首先,确定要使用的桶的数量。通常,桶的数量可以根据数据范围和分布情况来确定。

  2. 分发数据:将待排序的元素按照一定的规则(例如,数值大小)分发到不同的桶中。

  3. 每个桶内排序:对每个桶内的元素进行排序。这可以使用任何排序算法,例如插入排序或快速排序。

  4. 合并桶:将每个桶内的元素按照桶的顺序合并,形成有序序列。

图示如下:

bucketsort.png

桶排序性能分析

  • 时间复杂度:桶排序的时间复杂度取决于数据的分布情况。在最理想的情况下,当数据均匀分布在各个桶中时,每个桶内的排序时间复杂度是 O ( 1 ) O(1) O(1),因此总体时间复杂度为 O ( n ) O(n) O(n)。但在最坏情况下,如果所有数据都分布在一个桶中,桶内排序的时间复杂度可以达到 O ( n 2 ) O(n^2) O(n2)。在平均情况下,桶排序通常表现为 O ( n ) O(n) O(n)

  • 空间复杂度:桶排序需要额外的存储空间来存储桶,因此空间复杂度为 O ( n + k ) O(n+k) O(n+k),其中 n 表示排序元素的个数,k 表示桶的数量。

  • 稳定性:桶排序通常是稳定的,即相等元素的相对顺序在排序后不会发生变化。

使用场景

桶排序适用于以下情况:

  • 数据分布相对均匀。

  • 数据范围已知,可以将数据映射到有限数量的桶中。

Java 代码实现

以下是使用 Java 实现桶排序的示例代码,其中每个桶中的元素排序使用的是快速排序,快速排序的详解请参考历史博文 深入了解快速排序:原理、性能分析与 Java 实现

public class Test {public static void main(String[] args) {int[] arr = new int[]{17,35,37,32,63,46,24};System.out.println("原始数组:"+ Arrays.toString(arr));bucketSort(arr);System.out.println("排序后的数组:"+ Arrays.toString(arr));}//桶排序public static void bucketSort(int[] arr){int maxVal = Arrays.stream(arr).max().getAsInt();int minVal = Arrays.stream(arr).min().getAsInt();//计算桶的数量,+1 是保证至少有1个桶来装数据int bucketCount  = (maxVal - minVal)/arr.length + 1;// 用于存储每个桶中元素的出现次数int[] order = new int[bucketCount];// 用于存储每个桶中的数据int[][] output = new int[bucketCount][arr.length];int len = arr.length;//每个桶中数据的范围,+1 是至少每个桶中的数据范围为1int rang =  (maxVal - minVal)/bucketCount +1;//将待排序的数组中的所有元素放入到桶中for(int i = 0; i < len; i++ ){//计算数组元素所在的桶int index = (arr[i] - minVal)  /  rang ;//将元素放入指定的桶output[index][order[index]] = arr[i];//添加桶元素的计数order[index]++;}System.out.println("桶计数数组为:"+ Arrays.toString(order));int k = 0;//遍历桶,将桶中的元素放入源数组中,并对其进行快速排序for(int i = 0; i < bucketCount; i++){int j ;if(order[i] > 0){// 将桶中的元素放入源数组中for(j = 0; j < order[i]; j++){arr[k++] = output[i][j];}//对桶中的元素进行快速排序quickSort(arr,k-j,k-1);}}}//快速排序的详解请参考历史博文 `深入了解快速排序:原理、性能分析与 Java 实现`public static void quickSort(int[] arr,int left,int right) {//递归结束条件left < rightif(left < right){// 通过分区函数得到基准元素的索引int pivotIndex = partition(arr, left, right);//递归对基准元素左边的子数组进行快速排序quickSort(arr,left,pivotIndex-1);//递归对基准元素右边的子数组进行快速排序quickSort(arr,pivotIndex+1,right);}}public static int partition(int[] arr,int left,int right) {// 选择最后一个元素作为基准元素int pivot = arr[right];int i = left;//循环数组,如果满足条件,则将满足条件的元素交换到arr[i],同时i++,循环完成之后i之前的元素则全部为小于基准元素的元素for (int j = left; j < right; j++) {if(arr[j] < pivot){if(j != i){int temp  = arr[i];arr[i] = arr[j];arr[j] = temp;}i++;}}// 交换 arr[i] 和基准元素int temp = arr[i];arr[i] = arr[right];arr[right] = temp;//返回基准元素的下标return i;}
}

输出结果为:

原始数组:[17, 35, 37, 32, 63, 46, 24]
桶计数数组为:[1, 1, 3, 0, 1, 0, 1]
排序后的数组:[17, 24, 32, 35, 37, 46, 63]

这是一个基本的桶排序实现示例。您可以根据实际需求和数据类型进行扩展和优化。

总结

总的来说,桶排序是一种简单但有效的排序算法,特别适用于某些特定范围内数据的排序,当数据分布均匀时,性能较好。然而,对于不均匀分布的数据,其性能可能下降,因此在实际应用中需要谨慎选择。

相关文章:

深入了解桶排序:原理、性能分析与 Java 实现

桶排序&#xff08;Bucket Sort&#xff09;是一种排序算法&#xff0c;通常用于将一组数据分割成有限数量的桶&#xff08;或容器&#xff09;&#xff0c;然后对每个桶中的数据进行排序&#xff0c;最后将这些桶按顺序合并以得到排好序的数据集。 桶排序原理 确定桶的数量&am…...

微店店铺所有商品数据接口,微店整店商品数据接口,微店店铺商品数据接口,微店API接口

微店店铺所有商品数据接口是一种允许开发者在其应用程序中调用微店店铺所有商品数据的API接口。利用这一接口&#xff0c;开发者可以获取微店店铺的所有商品信息&#xff0c;包括商品名称、价格、介绍、图片等。 其主要用途是帮助开发者进行各种业务场景的构建&#xff0c;例如…...

SSL证书能选择免费的吗?

当涉及到保护您的网站和您的用户的数据时&#xff0c;SSL证书是必不可少的。SSL证书是一种安全协议&#xff0c;用于加密在Web浏览器和服务器之间传输的数据&#xff0c;例如信用卡信息、登录凭据和个人身份信息。 但是&#xff0c;许多SSL证书都是付费的&#xff0c;这可能会…...

苹果macOS电脑版 植物大战僵尸游戏

植物大战僵尸是一款极富策略性的小游戏&#xff0c;充满趣味性和策略性。主题是植物与僵尸之间的战斗。玩家通过武装多种不同的植物&#xff0c;切换不同的功能&#xff0c;快速有效地把僵尸阻挡在入侵的道路上。不同的敌人&#xff0c;不同的玩法构成五种不同的游戏模式&#…...

【每日一题】ABC311G - One More Grid Task | 单调栈 | 简单

题目内容 原题链接 给定一个 n n n 行 m m m 列的矩阵&#xff0c;问权值最大的子矩阵的权值是多少。 对于一个矩阵&#xff0c;其权值定义为矩阵中的最小值 m i n v minv minv 乘上矩阵中所有元素的和。 数据范围 1 ≤ n , m ≤ 300 1\leq n,m \leq 300 1≤n,m≤300 1 ≤…...

第五十六章 学习常用技能 - 执行 SQL 查询

文章目录 第五十六章 学习常用技能 - 执行 SQL 查询执行 SQL 查询检查对象属性 第五十六章 学习常用技能 - 执行 SQL 查询 执行 SQL 查询 要运行 SQL 查询&#xff0c;请在管理门户中执行以下操作&#xff1a; 选择系统资源管理器 > SQL。如果需要&#xff0c;请选择标题…...

2023年起重信号司索工(建筑特殊工种)证考试题库及起重信号司索工(建筑特殊工种)试题解析

题库来源&#xff1a;安全生产模拟考试一点通公众号小程序 2023年起重信号司索工(建筑特殊工种)证考试题库及起重信号司索工(建筑特殊工种)试题解析是安全生产模拟考试一点通结合&#xff08;安监局&#xff09;特种作业人员操作证考试大纲和&#xff08;质检局&#xff09;特…...

《华为战略管理法:DSTE实战体系》作者谢宁老师受邀为某电力上市集团提供两天的《成功的产品管理及产品经理》内训。

​​ 近日&#xff0c;《华为战略管理法&#xff1a;DSTE实战体系》作者谢宁老师受邀为某电力上市集团提供两天的《成功的产品管理及产品经理》内训。 谢宁老师作为华为培训管理部特聘资深讲师和顾问&#xff0c;也是畅销书《华为战略管理法&#xff1a;DSTE实战体系》、《智慧…...

finalshell连接虚拟机中的ubuntu

finalshell下载地址: https://www.finalshell.org/ubuntu设置root密码&#xff1a; sudo passwd rootubuntu关闭防火墙&#xff1a; sudo ufw disable安装ssh # sudo apt update #更新数据(可以不执行) # sudo apt upgrade #更新软件(可以不执行) sudo apt install open…...

django系列之事务操作

Django 默认的事务行为是自动提交&#xff0c;除非事务正在执行&#xff0c;否则每个查询将会马上自动提交到数据库。 1. 全局开启事务 在 Web 里&#xff0c;处理事务比较常用的方式是将每个请求封装在一个事务中。 在你想启用该行为的数据库中&#xff0c;把 settings 配置…...

stm32学习笔记:中断的应用:对射式红外传感器计次旋转编码器计次

相关API介绍 EXT配置API(stm32f10x exti.h&#xff09; NVIC 配置API (misc.h) 初始化的中断的步骤 第一步&#xff1a;配置RCC时钟&#xff0c;把涉及外设的时钟都打开 第二步&#xff1a;配置GPIO&#xff0c;设置为输入模式 第三步&#xff1a;配置AFIO&#xff0…...

one-hot是什么

“one-hot” 是一种编码技术&#xff0c;通常用于机器学习和数据处理中&#xff0c;用来表示分类数据或离散变量。它的目的是将一个分类变量转换成二进制向量&#xff0c;其中只有一个元素是 “hot”&#xff08;值为1&#xff09;&#xff0c;而其他元素都是 “cold”&#xf…...

基于阿基米德优化优化的BP神经网络(分类应用) - 附代码

基于阿基米德优化优化的BP神经网络&#xff08;分类应用&#xff09; - 附代码 文章目录 基于阿基米德优化优化的BP神经网络&#xff08;分类应用&#xff09; - 附代码1.鸢尾花iris数据介绍2.数据集整理3.阿基米德优化优化BP神经网络3.1 BP神经网络参数设置3.2 阿基米德优化算…...

ubuntu20.04配置阿里的kubernetes源

不仅适用于kubernetes软件源的配置&#xff0c;同样适用于其他软件源 1、安装依赖 sudo apt-get update # apt-transport-https may be a dummy package; if so, you can skip that package sudo apt-get install -y apt-transport-https ca-certificates curl 2、配置gpg签名…...

【运维】一些团队开发相关的软件安装。

gitlab 安装步骤 (1) 下载镜像&#xff0c;并且上传到服务器 https://mirrors.tuna.tsinghua.edu.cn/gitlab-ce/yum/el7/gitlab-ce-16.2.8-ce.0.el7.x86_64.rpm &#xff08;2&#xff09;rpm -i gitlab-ce-16.2.8-ce.0.el7.x86_64.rpm &#xff08;3&#xff09;安装成功后…...

互联网Java工程师面试题·Java 并发编程篇·第七弹

目录 16、CAS 的问题 17、什么是 Future&#xff1f; 18、什么是 AQS 19、AQS 支持两种同步方式&#xff1a; 20、ReadWriteLock 是什么 21、FutureTask 是什么 22、synchronized 和 ReentrantLock 的区别 23、什么是乐观锁和悲观锁 24、线程 B 怎么知道线程 A 修改了…...

SQL语句常见分类

SQL是Structured Query Language&#xff08;结构化查询语言&#xff09;的简写。 Structured发音 SQL 是关系型数据库管理系统的标准语言&#xff0c;如Oracle、MySQL、Microsoft SQL Server。 DDL DDL是Data Definition Language&#xff08;数据定义语言&#xff09;的简…...

SpringBoot通过配置切换注册中心(多注册中心nacos和eureka)

场景&#xff1a; 因项目需要&#xff0c;一个springcloud微服务工程需要同时部署到A,B两个项目使用&#xff0c;但A项目使用Eureka注册中心&#xff0c;B项目使用Nacos注册中心&#xff0c;现在需要通过部署时修改配置来实现多注册中心的切换。 解决思路&#xff1a; 如果同时…...

自动驾驶学习笔记(三)——场景设计

#Apollo开发者# 学习课程的传送门如下&#xff0c;当您也准备学习自动驾驶时&#xff0c;可以和我一同前往&#xff1a; 《自动驾驶新人之旅》免费课程—> 传送门 《2023星火培训【感知专项营】》免费课程—>传送门 文章目录 前言 场景设计平台 场景地图 场景基本…...

第 115 场 LeetCode 双周赛题解

A 上一个遍历的整数 模拟 class Solution { public:vector<int> lastVisitedIntegers(vector<string> &words) {vector<int> res;vector<int> li;for (int i 0, n words.size(); i < n;) {if (words[i] ! "prev")li.push_back(stoi…...

19c补丁后oracle属主变化,导致不能识别磁盘组

补丁后服务器重启&#xff0c;数据库再次无法启动 ORA01017: invalid username/password; logon denied Oracle 19c 在打上 19.23 或以上补丁版本后&#xff0c;存在与用户组权限相关的问题。具体表现为&#xff0c;Oracle 实例的运行用户&#xff08;oracle&#xff09;和集…...

Zustand 状态管理库:极简而强大的解决方案

Zustand 是一个轻量级、快速和可扩展的状态管理库&#xff0c;特别适合 React 应用。它以简洁的 API 和高效的性能解决了 Redux 等状态管理方案中的繁琐问题。 核心优势对比 基本使用指南 1. 创建 Store // store.js import create from zustandconst useStore create((set)…...

R语言AI模型部署方案:精准离线运行详解

R语言AI模型部署方案:精准离线运行详解 一、项目概述 本文将构建一个完整的R语言AI部署解决方案,实现鸢尾花分类模型的训练、保存、离线部署和预测功能。核心特点: 100%离线运行能力自包含环境依赖生产级错误处理跨平台兼容性模型版本管理# 文件结构说明 Iris_AI_Deployme…...

通过Wrangler CLI在worker中创建数据库和表

官方使用文档&#xff1a;Getting started Cloudflare D1 docs 创建数据库 在命令行中执行完成之后&#xff0c;会在本地和远程创建数据库&#xff1a; npx wranglerlatest d1 create prod-d1-tutorial 在cf中就可以看到数据库&#xff1a; 现在&#xff0c;您的Cloudfla…...

Linux云原生安全:零信任架构与机密计算

Linux云原生安全&#xff1a;零信任架构与机密计算 构建坚不可摧的云原生防御体系 引言&#xff1a;云原生安全的范式革命 随着云原生技术的普及&#xff0c;安全边界正在从传统的网络边界向工作负载内部转移。Gartner预测&#xff0c;到2025年&#xff0c;零信任架构将成为超…...

TRS收益互换:跨境资本流动的金融创新工具与系统化解决方案

一、TRS收益互换的本质与业务逻辑 &#xff08;一&#xff09;概念解析 TRS&#xff08;Total Return Swap&#xff09;收益互换是一种金融衍生工具&#xff0c;指交易双方约定在未来一定期限内&#xff0c;基于特定资产或指数的表现进行现金流交换的协议。其核心特征包括&am…...

Android15默认授权浮窗权限

我们经常有那种需求&#xff0c;客户需要定制的apk集成在ROM中&#xff0c;并且默认授予其【显示在其他应用的上层】权限&#xff0c;也就是我们常说的浮窗权限&#xff0c;那么我们就可以通过以下方法在wms、ams等系统服务的systemReady()方法中调用即可实现预置应用默认授权浮…...

大语言模型(LLM)中的KV缓存压缩与动态稀疏注意力机制设计

随着大语言模型&#xff08;LLM&#xff09;参数规模的增长&#xff0c;推理阶段的内存占用和计算复杂度成为核心挑战。传统注意力机制的计算复杂度随序列长度呈二次方增长&#xff0c;而KV缓存的内存消耗可能高达数十GB&#xff08;例如Llama2-7B处理100K token时需50GB内存&a…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

在QWebEngineView上实现鼠标、触摸等事件捕获的解决方案

这个问题我看其他博主也写了&#xff0c;要么要会员、要么写的乱七八糟。这里我整理一下&#xff0c;把问题说清楚并且给出代码&#xff0c;拿去用就行&#xff0c;照着葫芦画瓢。 问题 在继承QWebEngineView后&#xff0c;重写mousePressEvent或event函数无法捕获鼠标按下事…...