数据结构 (35)分配类排序

前言

       分配类排序是数据结构中的一种重要排序方法,其核心思想是利用分配和收集过程对元素进行排序,而无需比较元素之间的关键字。这种方法突破了基于关键字比较的排序算法的时间下界,可以达到线性时间复杂度O(n)。

一、分配类排序的基本概念

       分配类排序主要包括桶排序和基数排序两大类。这两类排序方法都遵循分配和收集的基本操作,但在具体实现上有所不同。

二、桶排序

  1. 工作原理:桶排序的工作原理是将数组分到有限数量的桶中,然后对每个桶中的元素进行排序。桶的数量和大小可以根据待排序数据的特点进行调整。

  2. 算法步骤

    • 划分桶:根据某种映射函数,将待排序数据的关键字映射到相应的桶中。
    • 桶内排序:对每个桶中的元素进行排序,可以使用其他排序算法,如快速排序。
    • 合并结果:将各个桶中的有序元素合并,得到最终的有序序列。
  3. 时间复杂度和空间复杂度:桶排序的时间复杂度取决于桶的数量和桶内排序算法的效率,通常为O(n*k),其中n为待排序数据的数量,k为桶的数量。空间复杂度为O(n+k),需要额外的空间来存储桶和桶内的元素。

三、基数排序

  1. 工作原理:基数排序是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。具体地,基数排序是按照低位先排序,然后收集;再按照高位排序,然后再收集;直到最高位。有时,基数排序也称为桶排序的扩展版本。

  2. 算法步骤(以链式基数排序为例):

    • 初始化队列:根据待排序数据的位数,创建相应数量的队列。
    • 分配过程:根据当前位数的值,将待排序数据分配到相应的队列中。
    • 收集过程:按照队列的顺序,将队列中的元素依次收集起来,形成新的待排序数据序列。
    • 重复步骤:对新的待排序数据序列重复上述分配和收集过程,直到所有位数都处理完毕。
  3. 时间复杂度和空间复杂度:基数排序的时间复杂度为O(n*k),其中n为待排序数据的数量,k为数据的最大位数。空间复杂度为O(n+k),需要额外的空间来存储队列和队列中的元素。

四、分配类排序的特点

  1. 无需比较:分配类排序不需要比较元素之间的关键字,从而避免了比较操作的开销。
  2. 线性时间复杂度:在最佳情况下,分配类排序可以达到线性时间复杂度O(n)。
  3. 适用场景:桶排序适用于数据分布均匀且桶的数量和大小选择合理的情况;基数排序适用于整数排序且数据位数较多的情况。

五、分配类排序的应用

       分配类排序在数据处理、数据挖掘、信息检索等领域有着广泛的应用。例如,在搜索引擎中,可以使用桶排序对搜索结果进行分页处理;在图像处理中,可以使用基数排序对像素值进行排序等。

 结语    

接纳自己的不完美

学会成长和进步

!!!

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

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

相关文章

sftp+sshpass

实现场景,要求客户端定时将本地的日志文件传输到服务器。 工作环境ubuntu,注意不通操作系统的版本不通,依赖的工具的版本也有所不同 实现目标需要客户端满足安装工具: 1、下载安装sshpass ---安装命令:sudo apt-ge…

Java 环境配置 + IntelliJ IDEA 使用指南

文章目录 一、Java 程序的运行必须经过3 个步骤:编写、编译、运行(1)Java 和 JavaScript 的区别(2)JDK、JRE、JVM 的关系(3)是否需要 Maven? 二、软件下载2.1、JDK下载与安装 —— 是…

013路由协议-OSPF

OSPF具有更适用于规模较大的网络环境,收敛更快速、依据带宽来计算路径成本等。 计算方式: 100M/当前端口的带宽 如果小于1就按照1来计算 例如: 当前端口的带宽是1.54M 路径成本 100/1.54 65 当前端口的带宽是 1000M 路径成本 100/100 0.…

刷题日志【4】

目录 1、猜数字大小 1、猜数字大小 题意有点抽象,我大概讲一下,就是在1——n里面会有一个目标数,我们通过猜数字的方式逼近这个数字,直到解出这个数,之前我们是用二分法求最快达到求解的问题,这道题多了每…

关于TDSQL(MySQL)的简单知识分享

0. 前言 最近在系统改造过程中,接触到了国产分布式数据库TDSQL,记录一下关于TDSQL的部分知识点。 1. TDSQL简介 TDSQL是腾讯推出的一款兼容MySQL的自主可控、高一致性分布式数据库产品。 1.1 TDSQL优点: 数据强一致性高性能低成本线性水…

学习记录:js算法(一百二十三):不同路径 II

文章目录 不同路径 II思路一 不同路径 II 给定一个 m x n 的整数数组 grid。一个机器人初始位于 左上角(即 grid[0][0])。机器人尝试移动到 右下角(即 grid[m - 1][n - 1])。机器人每次只能向下或者向右移动一步。 网格中的障碍物…

优秀的3d建模是数据可视化的视觉核心2

空间与深度感知的增强:3D建模提供了数据的三维表示,使得用户能够直观地理解数据在空间中的分布和关系。这种深度感知是二维数据可视化无法比拟的,它有助于揭示数据之间的隐藏联系和模式。 复杂数据的直观化:对于高维或复杂的数据集…

在Docker中运行MySQL的思考:挑战与解决方案

引言 在云计算和容器化技术日益普及的今天,Docker作为一种轻量级的容器化平台,已经成为开发和部署应用的首选工具之一。其提供的便携性、可扩展性和环境一致性对于无状态微服务来说无疑是巨大的福音。然而,并非所有应用都适合在Docker容器中…

Jenkins流水线初体验(六)

DevOps之安装和配置 Jenkins (一) DevOps 之 CI/CD入门操作 (二) Sonar Qube介绍和安装(三) Harbor镜像仓库介绍&安装 (四) Jenkins容器使用宿主机Docker(五) Jenkins流水线初体验(六) 一、Jenkins流水线任务介绍 之前采用Jenkins的自由风格构建的项目,每个步骤…

cdh agent 龙蜥系统安装

1、环境配置(都在cdh_install.gz.tar和cdh.gz.tar中) #安装JDK rpm -ivh jdk-8u191-linux-x64.rpm#安装时间同步 yum install ntp vi /etc/ntp.conf #将server 0.centos.pool.ntp.org iburst注释 #server 0.centos.pool.ntp.org iburst #server 1.centos.pool.ntp.org iburst …

微信小程序开发之tcp客户端开发

一、前提 首先,保证基础库不能低于2.18.0 二、tcp实现 微信小程序提供了 wx.createTCPSocket API,允许我们创建 TCP 连接。 示例:TCP 连接的基本使用 const tcpSocket wx.createTCPSocket()tcpSocket.onConnect(() > {console.log(TCP …

6.2 JavaScript Apis - 事件流

6.2 JavaScript Apis -事件流、事件委托 文章目录 6.2 JavaScript Apis -事件流、事件委托一、事件流1.1 事件捕获1.2 事件冒泡1.3 阻止冒泡1.4 解绑事件1.5 阻止默认行为 二、事件委托2.1 介绍2.2 tab栏切换改造 三、其他事件3.1 页面加载事件3.1.1 load 事件3.1.2 DOMContent…

利用Docker分层构建优化镜像大小

合适docker镜像文件大小不仅影响容器启动效率,也影响资源占用效率。本文介绍如何利用分层方式构建docker镜像,采用多种方式避免镜像文件太大而影响性能。 Docker 镜像大小优化的重要性 资源利用效率 较小的镜像文件在存储和传输过程中占用更少的空间和带…

SpringBoot3整合SpringMVC

一、实现过程: (1).创建程序 (2).引入依赖: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0"xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:schemaLocation"…

【C++】闰年判断问题完整解析与代码优化

博客主页&#xff1a; [小ᶻ☡꙳ᵃⁱᵍᶜ꙳] 本文专栏: C 文章目录 &#x1f4af;前言&#x1f4af;题目描述&#x1f4af;我的解法分析 &#x1f4af;老师解法分析代码 1&#xff08;未优化版本&#xff09;分析 代码 2&#xff08;优化版本&#xff09;分析 &#x1f4af…

【深度学习】深刻理解ViT

ViT&#xff08;Vision Transformer&#xff09;是谷歌研究团队于2020年提出的一种新型图像识别模型&#xff0c;首次将Transformer架构成功应用于计算机视觉任务中。Transformer最初应用于自然语言处理&#xff08;如BERT和GPT&#xff09;&#xff0c;而ViT展示了其在视觉任务…

深度学习实验十四 循环神经网络(1)——测试简单循环网络的记忆能力和梯度爆炸实验

目录 一、数据集构建 1.1数据集的构建函数 1.2加载数据集并划分 1.3 构建Dataset类 二、模型构建 2.1嵌入层 2.2SRN层 2.3模型汇总 三、模型训练 3.1 训练指定长度的数字预测模型 3.2 损失曲线展示 四、模型评价 五、修改 附完整可运行代码 实验大体步骤&#x…

js:我要在template中v-for循环遍历这个centrerTopdata,我希望自循环前面三个就可以了怎么写

问&#xff1a; 我按在要在template中v-for循环遍历这个centrerTopdata&#xff0c;我希望自循环前面三个就可以了怎么写&#xff1f; 回答&#xff1a; 问&#xff1a; <div v-for"(item, index) in centrerTopdata.slice(0, 3)" :key"index"> d…

2、开发环境优化与创建第一个插件程序

一、创建测试用例二、vscode优化2.1 修改默认终端为普通cmd2.2 配置一键编译&&运行&&监视一、创建测试用例 使用命令yo code生成一个测试用例,选择或输入下面的内容。2. 命令的最后会提示是否使用vscode打开,选择打开就行。 3. 在当前目录下会产生helloworld…

element-ui实现table表格的嵌套(table表格嵌套)功能实现

最近在做电商类型的官网&#xff0c;希望实现的布局如下&#xff1a;有表头和表身&#xff0c;所以我首先想到的就是table表格组件。 表格组件中常见的就是&#xff1a;标题和内容一一对应&#xff1a; 像效果图中的效果&#xff0c;只用基础的表格布局是不行的&#xff0c;因…