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

(十七)排序算法-基数排序

1 基本介绍

1.1 概述

(1)基数排序(radix sort)属于“分配式排序”,顾名思义,它是通过键值的各个位的值,将要排序的元素分配至某些“桶”中,达到排序的作用。
(2)基数排序是属于稳定性的排序,基数排序法是效率高的稳定性排序法。
(3)基数排序是桶排序的扩展。
(4)基数排序是1887年赫尔曼.何乐礼发明的。它是这样实现的:将整数按位数切割成不同的数字,然后按每个位数分别比较。

1.2 算法详解

首先基数排序是根据数位来进行排序的。它是从个位开始,然后按照每一位的数进行排序,如下图所示:
在这里插入图片描述
排完序之后就往前进一位,然后再将所有的数按照这一位所在的数进行排序,如下图所示:
在这里插入图片描述
重复这个过程直到所有的位数都已经被排过序了。如下图所示:
在这里插入图片描述
并且如果这个过程中碰到某个数在这个为上没有数的话就进行补零操作,将该位看成是0。就比方下图用红框圈出来的部分:
在这里插入图片描述
等到所有的位数都已经排序完毕之后,就可以看到已经排序好的序列了。

这个过程很好理解,但是如果是第一次看这个算法的肯定会有一个的困惑,那就是为什么基数排序选择的是从低位到高位来进行排序的,而不是像平常比较数据的大小一样,从高位到低位来比较呢?

这里先不讲为什么,先看下面这两个案例:

  • 从高位到低位进行比较
原序列百位排好序后十位排好序后个位排好序后
329839657839
457720457329
657657355657
839457839457
436436436436
720329720355
355355329720
  • 从低位到高位进行比较
原序列个位排好序后十位排好序后百位排好序后
329720720329
457355329355
657436436436
839457839457
436657355657
720329457720
355839655839

对比看了上面两个例子之后相信大家就知道了,很明显,如果是从高到低位来进行比较的话,会发现比较到最后之后序列仍然是无序的,但是从低位到高位进行比较的话,就会发现序列到最后已经排好序了。

是不是很奇怪,同样的执行过程,只不过执行的顺序发生了改变,为什么结果就回产生这样的结果呢?产生这个差异的重点就是在我们忽略了一个问题,那就是在进行高位到低位比较的时候,高位的权重是高于低位的。就比方下图所示:
在这里插入图片描述
正是因为这个原因,所以采取的是从低位到高位比较的过程.

说完基本思想之后,来说一下算法的实现步骤:

  1. 第一次遍历序列.找出序列中的最大值MAX,找到MAX之后,可以确定,需要比较多少数位了。
  2. 这时候,就需要按照元素在该位数对应的数字将元素存入到相应的容器之中。如下图所示:

在这里插入图片描述

  1. 之后再按照容器的顺序将元素重新弹出,构成接下来需要排序的序列,如下图所示:
    在这里插入图片描述
  2. 最后只需要重复2,3步骤,直到最高位也比较完毕,那么整个基数排序就已经完成了。

算法图解:
在这里插入图片描述

2 代码实现

/*** 基数排序*/
public class RadixSort {public static void main(String[] args) {int[] arr = {53, 3, 542, 478, 14, 241, 2, 23};radixSort(arr);System.out.println(Arrays.toString(arr));}// 基数排序方法public static void radixSort(int[] arr) {// 得到数组中最大的数的位数int max = arr[0];for (int i = 1; i < arr.length; i++) {if (arr[i] > max) {max = arr[i];}}// 得到最大数的位数,决定循环几轮int maxLength = (max + "").length();// 定义一个二维数组,表示10个桶,每个桶就是一个一维数组// 说明// 1. 二维数组包含10个一维数组// 2. 为了防止在放入数的时候,数据溢出,则每一个一维数组(桶),大小定为 arr.length// 3. 明确,基数排序是使用空间换时间的经典算法int[][] bucket = new int[10][arr.length];// 为了记录每个桶中,实际存放了多少个数据,定义一个一维数组来记录各个桶的每次放入的数据个数int[] bucketElementCounts = new int[10];// 循环 maxLength 轮for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {// 针对每个元素的对应位进行排序for (int j = 0; j < arr.length; j++) {// 取出每个元素的对应位的值int digitOfElement = arr[j] / n % 10;// 放入到对应的桶中bucket[digitOfElement][bucketElementCounts[digitOfElement]] = arr[j];bucketElementCounts[digitOfElement]++;}// 按照这个桶的顺序,依次取出数据,放入到原来数组int index = 0;for (int k = 0; k < bucketElementCounts.length; k++) {// 如果桶中有数据,放入到原数组if(bucketElementCounts[k] != 0){// 循环该桶,即第k个桶,放入for (int l = 0; l < bucketElementCounts[k]; l++) {arr[index++] = bucket[k][l];}}// 第 i+1 轮处理后,需要将每个 bucketElementCounts[k]=0bucketElementCounts[k] = 0;}System.out.println("第" + (i+1) + "轮,对位数的排序处理 arr=" + Arrays.toString(arr));}}
}

3 复杂度分析

  • 时间复杂度
    基数排序只需要根据最大元素的位数,遍历相应次数的序列即可,所以可以确定基数排序的时间复杂度一定是线性级别的,虽然是线性级别的,但是有一个系数的,这个系数就是最大元素的位数K,所以时间复杂度应该是O(n*k)。
  • 空间复杂度
    空间复杂度主要取决于链表的数量以及序列元素的数量,所以空间复杂度为O(n+k)。

相关文章:

(十七)排序算法-基数排序

1 基本介绍 1.1 概述 &#xff08;1&#xff09;基数排序&#xff08;radix sort&#xff09;属于“分配式排序”&#xff0c;顾名思义&#xff0c;它是通过键值的各个位的值&#xff0c;将要排序的元素分配至某些“桶”中&#xff0c;达到排序的作用。 &#xff08;2&#x…...

JMM之先行发生原则(happens-before)详解

1、概述 在JMM规范下&#xff0c;如果一个操作执行的结果需要对另一个操作可见&#xff0c;那么这两个操作之间必须存在happers-before(先行发生)原则。 例如 int x 10 ; int y x; 这两行代码中第二个操作 yx &#xff0c;因为需要将x值赋值给y&#xff0c;所以第一行代码的…...

含分布式电源的配电网可靠性评估研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

安全加固服务是什么?哪些行业需要做?

安全加固服务是什么&#xff1f;安全加固服务是一种针对企业信息系统、网络设备、应用程序等进行安全加固和优化的服务。安全加固服务的主要目的是保障企业信息系统的安全性和稳定性&#xff0c;有效防范各类网络攻击和安全威胁。 安全加固服务是什么&#xff1f;通常包括以下…...

好程序员:Java书籍推荐,程序员必看的5本Java书籍,赶紧收藏!

今天好程序员给大家推荐5本Java书籍&#xff0c;各大高校都在使用&#xff08;具体名单如下&#xff09;&#xff0c;所有学习Java的程序员都不应该错过&#xff01; 第一本Java书籍《Java EE&#xff08;SSM框架&#xff09;企业应用实战》 本书全面介绍了JavaEE中MyBatis、Sp…...

maven将jar包添加到本地仓库

第一步&#xff1a;下载需要添加的jar包 可以在maven库中查找下载&#xff0c;也可以在对应官网下载 maven库网址&#xff1a;https://mvnrepository.com/ 找到对应版本的jar包下载 第二步&#xff1a;将下载的jar包放到指定位置&#xff08;位置自己指定&#xff09;&#xf…...

4.12--计算机网络之TCP篇之TCP 协议的缺陷+如何基于 UDP 协议实现可靠传输?--(复习+大总结)---沉下心来(加油呀)

TCP 协议四个方面的缺陷&#xff1a; 1.升级 TCP 的工作很困难&#xff1b; TCP 协议是在内核中实现的&#xff0c;应用程序只能使用不能修改&#xff0c;如果要想升级 TCP 协议&#xff0c;那么只能升级内核。 而升级内核这个工作是很麻烦的事情 2.TCP 建立连接的延迟&#x…...

数据库网络编程

数据库网络编程是一个重要的领域&#xff0c;它涉及到如何使用编程语言与数据库进行交互&#xff0c;以及如何设计和实现网络应用程序。在这篇文章中&#xff0c;我将探讨数据库网络编程的基础知识、常用技术和实践经验&#xff0c;以及一些应用案例和未来发展趋势。 一、基础…...

为什么现代企业都在使用ERP系统 它有哪些优势

随着科技的不断发展&#xff0c;企业管理方式也在不断地发生改变。在这个信息化的时代&#xff0c;企业要想取得成功&#xff0c;必须要善于利用先进的信息化技术工具。其中&#xff0c;ERP系统是企业管理中不可或缺的重要工具。本文将探讨现代企业为什么会使用ERP系统&#xf…...

别再用 BeanUtils 了,这款 PO VO DTO 转换神器不香么?

老铁们是不是经常为写一些实体转换的原始代码感到头疼&#xff0c;尤其是实体字段特别多的时候。介绍一个开源项目 mapstruct &#xff0c;可以轻松优雅的进行转换&#xff0c;简化你的代码。当然有的人喜欢写get set&#xff0c;或者用BeanUtils 进行复制&#xff0c;代码只是…...

LeetCode算法小抄-- 最近公共祖先 和 完全二叉树的节点个数

LeetCode算法小抄-- 最近公共祖先 和 完全二叉树的节点个数 最近公共祖先[236. 二叉树的最近公共祖先](https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/)[235. 二叉搜索树的最近公共祖先](https://leetcode.cn/problems/lowest-common-ancestor-of-a-b…...

php、redis实现分布式锁的正确写法(原子操作 通用类 加讲解)

最终代码(通用类) 1 面试中、实际工作中&#xff0c;经常涉及到 redis 分布式锁&#xff0c;正确写法如下。先奉上代码&#xff0c;再讲解。 <?php namespace app\common\library; /*** 通用分布式锁(原子操作)*/ class Lock {/*** 获取redis实例* return \Redis* throws…...

Transformer在时序预测的应⽤第一弹——Autoformer

Transformer在时序预测的应⽤第一弹——Autoformer 原文地址&#xff1a;Autoformer: Decomposition Transformers with Auto-Correlation for Long-Term Series Forecasting&#xff08;NIPS 2021&#xff09; 做长时间序列的预测 Decomposition把时间序列做拆分&#xff0c…...

文章改写神器在线-AI续写文章生成器

AI续写生成器 AI续写生成器是一种利用人工智能技术的创意工具&#xff0c;能够提高写作效率&#xff0c;为营销推广带来全新的可能性。无论你是写手、广告人员还是市场营销人员&#xff0c;这个工具都能够有效地解决你在写作中遇到的难题。 在内容创作行业中&#xff0c;原创…...

一秒钟给硬盘文件做个树状结构目录

一秒钟给硬盘文件做个树状结构目录 一、背景 对于长时间坐在电脑前的打工人来说&#xff0c;若没有养成良好文件分类习惯的话&#xff0c;年终整理电脑文件绝对是件头疼的事情。 给磁盘文件做个目录&#xff0c;一目了然文件都在哪里&#xff1f;想想都是件头疼的事情。 对于…...

电脑重装系统后会怎样?

​有小伙伴的电脑系统运行缓慢卡顿&#xff0c;现在想通过重装系统来解决问题。咨询电脑重装系统会怎么样对系统有影响吗&#xff0c;现在小编就带大家看看电脑重装系统后会怎样。 方法/步骤&#xff1a; 一、电脑重装系统会怎么样 1、我们的电脑重装系统后&#xff0c;电脑…...

100种思维模型之反熵增思维模型-47

查理芒格被誉为反熵增思维模型的倡导者。本文将介绍查理芒格的反熵增思维模型&#xff0c;并分析它的实用性。 一、什么是熵增&#xff1f; 在物理学中&#xff0c;熵是衡量系统无序程度的指标。系统的熵越高&#xff0c;其无序程度越高。这个概念也可以应用到其他领域。在金融…...

【网络安全】Xss漏洞

xss漏洞 xss漏洞介绍危害防御方法xss测试语句xss攻击语句1. 反射性xss2.存储型xss3.DOM型xssdvwa靶场各等级渗透方法xss反射型&#xff08;存储型方法一致&#xff09;LowMediumHightimpossible Dom型LowMediumHight xss漏洞介绍 定义&#xff1a;XSS 攻击全称跨站脚本攻击&am…...

17.网络爬虫—Scrapy入门与实战

这里写目录标题 Scrapy基础Scrapy运行流程原理Scrapy的工作流程Scrapy的优点 Scrapy基本使用(豆瓣网为例)创建项目创建爬虫配置爬虫运行爬虫如何用python执行cmd命令数据解析打包数据打开管道pipeline使用注意点 后记 前言&#xff1a; &#x1f3d8;️&#x1f3d8;️个人简介…...

【面试题】JavaScript 中 try...catch 的使用技巧 ?

大厂面试题分享 面试题库 前后端面试题库 &#xff08;面试必备&#xff09; 推荐&#xff1a;★★★★★ 地址&#xff1a;前端面试题库 web前端面试题库 VS java后端面试题库大全 作为一位 Web 前端工程师&#xff0c;JavaScript 中的 try...catch 是我们常用的特性之一。…...

【根据当天日期输出明天的日期(需对闰年做判定)。】2022-5-15

缘由根据当天日期输出明天的日期(需对闰年做判定)。日期类型结构体如下&#xff1a; struct data{ int year; int month; int day;};-编程语言-CSDN问答 struct mdata{ int year; int month; int day; }mdata; int 天数(int year, int month) {switch (month){case 1: case 3:…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

(十)学生端搭建

本次旨在将之前的已完成的部分功能进行拼装到学生端&#xff0c;同时完善学生端的构建。本次工作主要包括&#xff1a; 1.学生端整体界面布局 2.模拟考场与部分个人画像流程的串联 3.整体学生端逻辑 一、学生端 在主界面可以选择自己的用户角色 选择学生则进入学生登录界面…...

三维GIS开发cesium智慧地铁教程(5)Cesium相机控制

一、环境搭建 <script src"../cesium1.99/Build/Cesium/Cesium.js"></script> <link rel"stylesheet" href"../cesium1.99/Build/Cesium/Widgets/widgets.css"> 关键配置点&#xff1a; 路径验证&#xff1a;确保相对路径.…...

无法与IP建立连接,未能下载VSCode服务器

如题&#xff0c;在远程连接服务器的时候突然遇到了这个提示。 查阅了一圈&#xff0c;发现是VSCode版本自动更新惹的祸&#xff01;&#xff01;&#xff01; 在VSCode的帮助->关于这里发现前几天VSCode自动更新了&#xff0c;我的版本号变成了1.100.3 才导致了远程连接出…...

使用 SymPy 进行向量和矩阵的高级操作

在科学计算和工程领域&#xff0c;向量和矩阵操作是解决问题的核心技能之一。Python 的 SymPy 库提供了强大的符号计算功能&#xff0c;能够高效地处理向量和矩阵的各种操作。本文将深入探讨如何使用 SymPy 进行向量和矩阵的创建、合并以及维度拓展等操作&#xff0c;并通过具体…...

嵌入式学习笔记DAY33(网络编程——TCP)

一、网络架构 C/S &#xff08;client/server 客户端/服务器&#xff09;&#xff1a;由客户端和服务器端两个部分组成。客户端通常是用户使用的应用程序&#xff0c;负责提供用户界面和交互逻辑 &#xff0c;接收用户输入&#xff0c;向服务器发送请求&#xff0c;并展示服务…...

系统掌握PyTorch:图解张量、Autograd、DataLoader、nn.Module与实战模型

本文较长&#xff0c;建议点赞收藏&#xff0c;以免遗失。更多AI大模型应用开发学习视频及资料&#xff0c;尽在聚客AI学院。 本文通过代码驱动的方式&#xff0c;系统讲解PyTorch核心概念和实战技巧&#xff0c;涵盖张量操作、自动微分、数据加载、模型构建和训练全流程&#…...

Python 训练营打卡 Day 47

注意力热力图可视化 在day 46代码的基础上&#xff0c;对比不同卷积层热力图可视化的结果 import torch import torch.nn as nn import torch.optim as optim from torchvision import datasets, transforms from torch.utils.data import DataLoader import matplotlib.pypl…...

2025-05-08-deepseek本地化部署

title: 2025-05-08-deepseek 本地化部署 tags: 深度学习 程序开发 2025-05-08-deepseek 本地化部署 参考博客 本地部署 DeepSeek&#xff1a;小白也能轻松搞定&#xff01; 如何给本地部署的 DeepSeek 投喂数据&#xff0c;让他更懂你 [实验目的]&#xff1a;理解系统架构与原…...