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

数据结构与算法之排序: 桶排序 (Javascript版)

排序

  • 排序:把某个乱序的数组变成升序或降序的数组 (这里用数组来做举例)

桶排序

  • 根据元素的取值范围,创建多个桶, 每个桶代表一个区间范围
    • 创建桶的数量和范围需要尽可能保证元素能够被均匀分布
  • 接下来将元素放进对应的桶中,分别对每个桶中的元素进行排序
    • 桶内采用的排序算法可自行决定
    • 均匀分布后,每个桶内元素数量不会很多
  • 最后,按顺序将桶里的元素取出就完成了排序
  • 桶排序用的并不多,主要体现在对于桶排序的应用: 计数排序基数排序
  • 核心思想
    • 基于最小值和最大值算出一个差值,基于差值确定桶的数量和范围
    • 之后遍历数组中的每个元素,来分配到不同的桶中
    • 对每一个桶进行单独的排序
    • 最后整合所有的桶,即可

算法实现

1 )定义桶数,均匀分布

// 获取当前在第几个桶里
function getIndex(period, currentDist) {if (currentDist <= period) return 0;return Math.floor(currentDist / period);
}// 桶排序 主函数 list 待排序数组, n是定义的桶数量
function bucketSort(list, n = 2) {// 计算最大值和最小值const max = Math.max.apply(null, list);const min = Math.min.apply(null, list);const dist = max - min; // 最大值和最小值两者差距let buckets = []; // 用于存放多个桶的总数组// n个桶, 每个桶内存放范围 dist / n 每个桶的间隔const period = Math.ceil(dist / n);// 将列表中的数据分配到不同的桶里list.forEach((current) => {const d = current - min; // 当前与最小值的差距,用于计算当前数据应该填充在哪个桶内const index = getIndex(period, d); // 基于桶数和当前值,算出应该存放到第几个桶内// 基于 index 来填充到对应的桶内!buckets[index] ? (buckets[index] = [current]) : buckets[index].push(current);});// 对 buckets 中的每个桶进行排序buckets.map((bucket) => {bucket.sort((a,b) => a - b); // 这个使用默认的排序,其实内部可以使用任意的排序算法return bucket;});// 对 buckets 中的每个桶进行合并 (拍平)buckets = buckets.toString().split(',');return buckets.map(item => item / 1);
}const list = [102,103,108,107,101,102,102,102,107,103,109,108,102,101,104,102,104,106,109,102];
const result = bucketSort(list, 5);
console.log(result); // [101, 101, 102, 102, 102, 102, 102, 102, 102, 103, 103, 104, 104, 106, 107, 107, 108, 108, 109, 109]

总结

  • 桶排序的时间复杂度 在 O(n) ~ O( n 2 n^2 n2)
  • 普通桶排序并不普遍应用是拆分为桶后,在每个桶内还需要排序,意义就不大了
    • 而且要考虑每个桶内用什么样的数据结构来存储(考虑到内部排序)
      • 如果还用数组就极大浪费了空间(需使用最大的空间, 不同语言有区别)
      • 一般可以使用链表,但是对链表排序又开始麻烦了
    • 桶排序优化空间,时间上就会增加;优化时间空间上又会增多, 取一个时间和空间的平衡
  • buckets.map 基本是常数级别,这里实际上不怎么会消耗时间, 具体的sort算法可以使用任意的排序算法实现
  • 关于怎么处理和分配桶,上述算法基于用户自行填入的桶数,来均匀处理, 也可传入所有桶的范围分布列表
  • 那算法的细节实现就会不一样,但基本思想是一致的
  • 虽然上述算法意义不大, 但是桶排序的意义在于其思想:分而治之, 分配处理, 桶作为基本单位
  • 这个桶排序算法在开发中是比较重要的一种思想

相关文章:

数据结构与算法之排序: 桶排序 (Javascript版)

排序 排序&#xff1a;把某个乱序的数组变成升序或降序的数组 (这里用数组来做举例) 桶排序 根据元素的取值范围&#xff0c;创建多个桶, 每个桶代表一个区间范围 创建桶的数量和范围需要尽可能保证元素能够被均匀分布 接下来将元素放进对应的桶中&#xff0c;分别对每个桶中…...

Android studio新版本多渠道打包配置

最近公司套壳app比较多 功能也都一样只有地址&#xff0c;和app名字还有icon不一样 签名文件也是一样的,所以就研究了多渠道打包 配置如下&#xff1a; 在app下build.gradle配置 因为最新版as中禁用了BuildConfig 所以我们需要手动配置一下 android { //TODO 其他省略buildFe…...

PTA:后序和中序构造二叉树

后序和中序构造二叉树 题目输入格式输出格式输入样例&#xff08;及其对应的二叉树&#xff09; 代码 题目 本题目要求用后序序列和中序序列构造一棵二叉树&#xff08;树中结点个数不超过10个&#xff09;&#xff0c;并输出其先序序列。 输入格式 在第一行中输入元素个数…...

二十三种设计模式全面解析-适配器模式的妙用:异构数据库和不同版本API的完美兼容!

在当今的软件开发领域&#xff0c;我们常常面对着与异构数据库和不同版本的API进行集成的挑战。这些系统和组件往往使用不同的数据结构和接口规范&#xff0c;导致我们的代码无法直接与它们进行交互。但是&#xff0c;不要担心&#xff01;今天&#xff0c;我将向你揭示一个神奇…...

K7系列FPGA进行FLASH读写1——CCLK控制(STARTUPE2原语)

最近的工作涉及对 FPGA 进行远程更新&#xff0c;也就是通过远程通信接口将 .bin 文件送到 FPGA&#xff0c;然后写入 FLASH&#xff0c;这样当 FPGA 重新上电后就可以执行更新后的程序了。因此第一步工作就是进行 FLASH 的读写控制。 然而如果尝试配置 FLASH 管脚时&#xff0…...

【Kafka】基本概念

文章目录 一、消息队列的流派1.1 有Broker1.1.1 重topic1.1.2 轻topic 1.2 无Broker 二、kafka安装三、kafka基本术语四、发送消息五、消费消息六、单播消息七、多播消息八、查看消费组的详细信息九、主题topic十、分区十一、kafka中消息⽇志⽂件中保存的内容 一、消息队列的流…...

如何在Vue3项目中使用防抖节流技巧

前言 防抖节流是可以说是一种优化组件性能的技巧&#xff0c;可以有效减少组件中的渲染次数和计算量&#xff0c;从而提高组件的响应速度和用户体验。在Vue3中可以使用lodash库中的debounce和throttle函数来分别实现防抖和节流。当然也可以自行设计实现防抖节流函数&#xff0…...

快速排序(Java)

基本思想 快速排序Quicksort&#xff09;是对冒泡排序的一种改进。 基本思想是分治的思想&#xff1a;通过一趟排序将要排序的数据分割成独立的两部分&#xff0c;其中一部分的所有数据都比另外一部分的所有数据都要小&#xff0c;然后再按此方法对这两部分数据分别进行快速排…...

在ffmpeg中,如何把h264转换为rgb格式

在ffmpeg中&#xff0c;网络视频流h264为什么默认的转为YUV而不是其他格式 文章中介绍了&#xff0c;h264解码的时候是直接解码为yuv的&#xff0c;如果在使用的过程中 需要用到rgb的格式&#xff0c;我们该如何来转换这种格式呢&#xff1f; 在上面的文章中&#xff0c;我们已…...

【重磅】Cookies、headers、Session规律总结,搞定卡点

【重磅】Cookies规律总结,搞定卡点 登录后开始正式获取数据阶段: 不使用session: 放在请求头headers中 当如是:headers = {“user-agent”: “Mozilla/5.0 (Windows NT 10.0; Win64; x64) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/104.0.0.0 Safari/537.36”,“Coo…...

【雷达原理】雷达杂波抑制方法

目录 一、杂波及其特点 1.1 什么是杂波&#xff1f; 1.2 杂波的频谱特性 二、动目标显示(MTI)技术 2.1 对消原理 2.2 数字对消器设计 三、MATLAB仿真 3.1 对消效果验证 3.2 代码 一、杂波及其特点 1.1 什么是杂波&#xff1f; 杂波是相对目标回波而言的&#xff0c;…...

Python-敲木鱼升级版(真手动版敲木鱼)

演示效果 需要安装的第三方库&#xff1a; pip install pygame # 加载音乐 pip install pillow # 加载图片 pip install mediapipe # 判断手势的模型 pip install opencv # 模型要用来处理图形 建议有独显和摄像头的可以尝试&#xff01; 想着升级一下玩法&#xff0c;只有真敲…...

Websocket @ServerEndpoint不能注入@Autowired

在websocket中使用ServerEndpoint无法注入Autowired、Value 问题分析 Spring管理采用单例模式&#xff08;singleton&#xff09;&#xff0c;而 WebSocket 是多对象的&#xff0c;即每个客户端对应后台的一个 WebSocket 对象&#xff0c;也可以理解成 new 了一个 WebSocket&…...

Unity热更新

1&#xff0c;热更新的概念与作用 app更新通常分为两类&#xff0c;一种是整包更新&#xff08;换包&#xff09;&#xff0c;一种是热更新&#xff08;不换包&#xff0c;通过网络下载&#xff0c;动态更新资源等&#xff09;。 整包更新&#xff0c;是指在需要更新时&#x…...

如何用维格云搭建和一键训练你的钧瓷AI机器人?

大禹智库 第69期(总第400期) 2023年11月4日 如何用维格云搭建和一键训练你的钧瓷AI机器人? 钧瓷私有数据聊天机器人是一种能够根据预设的数据集进行智能对话的机器人。通过维格云,我们可以轻松地搭建自己的钧瓷私有数据聊天机器人。本文将以钧道机器人为例,详细介绍如何…...

整理的一些Java细节问题

1. 为什么要有无参构造&#xff1f; 在 Java 中&#xff0c;如果一个类没有显式定义构造方法&#xff0c;编译器会自动生成一个默认的无参构造方法&#xff08;也称为默认构造方法&#xff09;。无参构造方法是一个没有任何参数的构造方法。 无参构造方法的存在有几个重要原因…...

初识AUTOSAR网络管理

文章目录 目的模式时间参数T_REPEAT_MESSAGET_NM_TIMEOUTT_WAIT_BUS_SLEEPT_START_Tx_AppFrameT_NM_ImmediateCycleTimeT_NM_MessageCycleN_ImmediateNM_TIMEST_START_NM_TXT_WakeUp跳转状态NM_1NM_2NM_3NM_4NM_5NM_6NM_7...

Flink SQL Hive Connector使用场景

目录 1.介绍 2.使用 2.1注册HiveCatalog 2.2Hive Read 2.2.1流读关键配置 2.2.2示例...

【Docker】联合探讨Docker:容器化技术的革命性应用

前言 Docker 是一个开源的应用容器引擎&#xff0c;让开发者可以打包他们的应用以及依赖包到一个可移植的容器中,然后发布到任何流行的Linux或Windows操作系统的机器上,也可以实现虚拟化,容器是完全使用沙箱机制,相互之间不会有任何接口。 &#x1f4d5;作者简介&#xff1a;热…...

dirhunt使用手册,中文版

“dirhunt” 的命令行工具的帮助信息&#xff0c;用于目录扫描和网站内容分析。以下是这个命令的使用方法和示例&#xff1a; 命令格式&#xff1a; dirhunt [OPTIONS] [URLS]… [URLS]…&#xff1a;一个或多个域名或 URL&#xff0c;可以加载来自文件的 URL&#xff0c;使用…...

AIGlasses_for_navigation基础教程:无需ESP32,纯Web端完成所有功能验证

AIGlasses_for_navigation基础教程&#xff1a;无需ESP32&#xff0c;纯Web端完成所有功能验证 1. 引言&#xff1a;从零开始&#xff0c;验证你的智能眼镜导航系统 你是不是也对那个集成了AI、传感器和导航功能的智能眼镜项目——AIGlasses_for_navigation——感到好奇&…...

RMBG-2.0应用案例:如何快速处理社交媒体配图

RMBG-2.0应用案例&#xff1a;如何快速处理社交媒体配图 1. 社交媒体配图的痛点与解决方案 在当今内容爆炸的时代&#xff0c;社交媒体配图的质量直接影响着内容的传播效果。无论是个人博主还是企业账号&#xff0c;每天都需要制作大量配图来吸引用户注意力。然而&#xff0c…...

Source Han Serif TTF:企业级中文排版战略选择与规模化部署指南

Source Han Serif TTF&#xff1a;企业级中文排版战略选择与规模化部署指南 【免费下载链接】source-han-serif-ttf Source Han Serif TTF 项目地址: https://gitcode.com/gh_mirrors/so/source-han-serif-ttf 思源宋体TTF作为Adobe与Google联合开发的开源中文字体解决方…...

ETS5保姆级教程:从零配置KNX智能开关,实现灯光、窗帘、场景联动

ETS5保姆级教程&#xff1a;从零配置KNX智能开关&#xff0c;实现灯光、窗帘、场景联动 KNX作为智能家居领域的国际标准协议&#xff0c;以其稳定性和灵活性备受推崇。而ETS5则是配置KNX系统的核心工具&#xff0c;掌握它意味着你能够自由定制属于自己的智能家居方案。本教程将…...

游戏开发实战:如何用Bezier曲线打造流畅的3D角色动画路径(Unity/C#示例)

游戏开发实战&#xff1a;如何用Bezier曲线打造流畅的3D角色动画路径&#xff08;Unity/C#示例&#xff09; 在3D游戏开发中&#xff0c;角色移动轨迹的自然度直接影响玩家体验。传统直线移动或简单弧线往往显得生硬&#xff0c;而Bezier曲线凭借其平滑过渡和灵活控制的特性&am…...

从L298到自举H桥:深入聊聊直流电机驱动方案的演进与选型心得

从L298到自举H桥&#xff1a;直流电机驱动方案的技术演进与工程实践 在机器人底盘、自动化产线和智能硬件开发中&#xff0c;直流电机驱动电路的设计往往决定着整个系统的性能天花板。十年前我们可能还在用L298这类经典驱动芯片&#xff0c;如今工程师们的工具箱里已经出现了IR…...

CSS图片轮播进阶:5种实现无限循环滚动的实战技巧(附完整代码)

CSS图片轮播进阶&#xff1a;5种实现无限循环滚动的实战技巧&#xff08;附完整代码&#xff09; 在电商网站的首页或个人作品集的展示页面中&#xff0c;图片轮播&#xff08;Carousel&#xff09;始终是吸引用户注意力的利器。而无限循环滚动效果&#xff0c;则能让有限的展示…...

nomic-embed-text-v2-moe保姆级教程:Gradio自定义CSS主题与响应式布局

nomic-embed-text-v2-moe保姆级教程&#xff1a;Gradio自定义CSS主题与响应式布局 1. 从零开始&#xff1a;认识nomic-embed-text-v2-moe 如果你正在寻找一个既强大又好用的文本嵌入模型&#xff0c;特别是需要处理多语言内容&#xff0c;那么nomic-embed-text-v2-moe绝对值得…...

QLVideo:macOS视频管理效率提升的完整解决方案

QLVideo&#xff1a;macOS视频管理效率提升的完整解决方案 【免费下载链接】QuickLookVideo This package allows macOS Finder to display thumbnails, static QuickLook previews, cover art and metadata for most types of video files. 项目地址: https://gitcode.com/g…...

别再只会用A4988了!用STM32+L298N手撸42步进电机细分驱动(附256细分算法)

从零构建STM32L298N的256细分步进电机驱动系统 在创客和嵌入式开发领域&#xff0c;步进电机控制一直是个既基础又充满挑战的课题。市面上常见的A4988、DRV8825等驱动模块虽然方便&#xff0c;但当项目需要更高精度、更灵活控制时&#xff0c;这些现成方案往往显得力不从心。本…...