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

基数排序算法解析与TypeScript实现

news 来源：原创 2025/9/8 17:56:38

基数排序（Radix Sort）是一种高效的非比较型整数排序算法，通过逐位分配与收集的方式实现排序。本文将深入解析其工作原理，并给出完整的TypeScript实现。

一、算法原理

1. 核心思想

多关键字排序：将整数按位数切割成不同数字
低位优先（LSD）：从最低有效位开始排序
稳定排序：保持相同值元素的原始顺序

2. 执行步骤

确定最大数的位数
从最低位开始到最高位循环：
- 分配：根据当前位数将元素放入0-9的桶中
- 收集：按顺序从各桶取出元素
重复直到处理完所有位数

二、算法特性

特性	描述
时间复杂度	O(n*k)（k为最大位数）
空间复杂度	O(n + k)
稳定性	稳定
最佳场景	整数排序，位数较少
最差场景	存在超大数值的整数

三、TypeScript实现

/*** 获取数字指定位的值* @param num 目标数字* @param digit 位数（从0开始，0表示个位）*/
const getDigit = (num: number, digit: number): number => {return Math.floor(Math.abs(num) / Math.pow(10, digit)) % 10;
}/*** 获取数字的最大位数* @param nums 数字数组*/
const getMaxDigits = (nums: number[]): number => {let maxDigits = 0;const maxNum = Math.max(...nums.map(Math.abs));while (maxNum >= Math.pow(10, maxDigits)) maxDigits++;return maxDigits;
}/*** 基数排序主函数* @param nums 待排序数组*/
const radixSort = (nums: number[]): number[] => {// 处理空数组和单元素数组if (nums.length < 2) return [...nums];// 分离正负数处理const negatives = nums.filter(n => n < 0).map(n => -n);const positives = nums.filter(n => n >= 0);// 排序正数部分const sortPart = (arr: number[]): number[] => {const maxDigits = getMaxDigits(arr);let sorted = [...arr];for (let digit = 0; digit < maxDigits; digit++) {const buckets: number[][] = Array.from({ length: 10 }, () => []);// 分配元素到桶中for (const num of sorted) {const bucketIndex = getDigit(num, digit);buckets[bucketIndex].push(num);}// 收集元素sorted = ([] as number[]).concat(...buckets);}return sorted;}// 合并排序结果const sortedNegatives = sortPart(negatives).reverse().map(n => -n);const sortedPositives = sortPart(positives);return [...sortedNegatives, ...sortedPositives];
}

四、使用示例

// 测试数据
const testData = [3, -1, 4, 1, -5, 9, 2, 6, 5, -3, 5];
const sorted = radixSort(testData);console.log('排序结果：', sorted);
// 输出：[-5, -3, -1, 1, 2, 3, 4, 5, 5, 6, 9]

五、代码解析

1. 负数处理策略

分离正负数单独处理
对负数取绝对值排序后反转再还原符号

2. 关键优化点

提前终止循环：当maxDigits为0时直接返回
内存复用：每次循环复用sorted数组
类型安全：严格定义桶的二维数组类型

3. 复杂度控制

时间复杂度：实际运行效率取决于最大数的位数
空间复杂度：主要消耗在桶的存储空间

六、适用场景

不适用场景

包含小数的数值排序
非数值型数据排序
存在超大数值（如超过10^15）的情况

七、性能对比

对比不同排序算法处理10万随机整数（0-10000）耗时：

算法	耗时（ms）
快速排序	15.2
归并排序	18.7
基数排序	9.8

八、扩展改进

1. 支持字母排序

const charRadixSort = (strs: string[]): string[] => {const maxLen = Math.max(...strs.map(s => s.length));for (let i = maxLen - 1; i >= 0; i--) {const buckets: string[][] = Array.from({ length: 256 }, () => []);for (const str of strs) {const charCode = str.charCodeAt(i) || 0;buckets[charCode].push(str);}strs = ([] as string[]).concat(...buckets);}return strs;
}

2. 并行优化

利用Web Worker多线程处理分配过程
分块处理超大数组

九、总结

基数排序展现了分治思想在整数排序中的独特优势，其：

线性时间复杂度的特性使其在大数据量场景表现突出
稳定排序的特性适合需要保持原始顺序的场景
可扩展性强，可适配各种基数类数据排序

理解基数排序不仅能提升算法设计能力，更能帮助开发者根据实际场景选择最优排序策略。当处理特定领域的数值排序问题时，基数排序往往是隐藏的性能利器。

如果对你有帮助，请帮忙点个赞

基数排序算法解析与TypeScript实现

基数排序（Radix Sort）是一种高效的非比较型整数排序算法，通过逐位分配与收集的方式实现排序。本文将深入解析其工作原理，并给出完整的TypeScript实现。一、算法原理 1. 核心思想多关键字排序：将整数按位数切割成不同…...

编程日记 2025/9/8 17:56:38

有关asm磁盘的命令添加磁盘 alter diskgroup data1 add disk /devices/diska*;---runs with a rebalance power of 5 , and dose not return until the rebalance operation is completealter diskgroup data1 add disk /devices/diskd* rebalance power 5 wait;查询 select …...

编程日记 2025/9/8 17:51:16

THUNLP_Multimodal_Excercise

背景多模态大模型（Multimodal Large Language Models, MLLM）的构建过程中，模型结构、模型预测、指令微调以及偏好对齐训练是其中重要的组成部分。本次任务中，将提供一个不完整的多模态大模型结构及微调代码，请根据要求…...

编程日记 2025/9/8 17:53:56

AIGC6——AI的哲学困境：主体性、认知边界与“天人智一“的再思考

引言：当机器开始"思考" 2023年，Google工程师Blake Lemoine声称对话AI LaMDA具有"自我意识"，引发轩然大波。这一事件将古老的哲学问题重新抛回公众视野：**机器能否拥有主体性？**从东方"天人…...

编程日记 2025/9/3 16:24:00

主题（topic）中使用键（key）来区分同一主题下的多个数据实例

在Fast DDS中，通过在主题（topic）中使用键（key）来区分同一主题下的多个数据实例，具体含义如下： 1. **主题（Topic）**：在DDS中，主题是数据的类型或类…...

编程日记 2025/9/8 12:38:33

[王阳明代数讲义]琴语言类型系统工程特性

琴语言类型系统工程特性层展物理学组织实务与艺术与琴生生.物机.械科.技工.业研究.所软凝聚态物理开发工具包社会科学气质砥砺学人生意气场社群成员魅力场与心气微积分社会关系力学意气实体过程图论信息编码，如来码导引注意力机制道装Transformer架构的发展标度律…...

编程日记 2025/9/8 17:53:16

蜜蜡是什么?蜜蜡与琥珀的区别以及蜜蜡的收藏价值一览

蜜蜡是琥珀的一种，在物理成分和化学成分上都和琥珀没有区别，只是因其“色如蜜，光如蜡”而得名。蜜蜡形成于白垩纪时期，因形成时间较长，形成过程比较复杂等原因，种类较其他产地要多。蜜蜡是有机矿物&#x…...

编程日记 2025/9/5 11:03:24

第五课：高清修复和放大算法

文章目录 Part.01 高清修复(Hi-Res Fix)Part.02 SD放大(SD Upscale)Part.03 附加功能放大Part.01 高清修复(Hi-Res Fix) 文生图中的高清修复/高分辨率修复/超分辨率修复先低分辨率抽卡，再高分辨率修复。不能突破显存限制放大重绘幅度安全范围是0.3-0.5，如果想让AI更有想象力0…...

编程日记 2025/9/8 17:52:40

SpringSecurity6.0 通过JWTtoken进行认证授权

之前写过一个文章，从SpringSecurity 5.x升级到6.0，当时是为了配合公司的大版本升级做的，里面的各项配置都是前人留下来的，其实没有花时间进行研究SpringSecurity的工作机制。现在新东家有一个简单的系统要搭建，用户的认…...

编程日记 2025/9/8 4:41:57

TypeScript工程集成

以下是关于 TypeScript 工程集成的系统梳理，涵盖基础配置、进阶优化、开发规范及实际场景的注意事项，帮助我们构建高效可靠的企业级 TypeScript 项目：一、基础知识点 1. 项目初始化与配置 tsconfig.json 核心配置：{"compilerOptions": {"target": &…...

编程日记 2025/9/8 17:55:58

网络空间安全（51）邮件函数漏洞

前言邮件函数漏洞，特别是在PHP环境中使用mail()函数时，是一个重要的安全问题。一、概述在PHP中，mail()函数是一个用于发送电子邮件的内置函数。其函数原型为： bool mail ( string $to , string $subject , string $message [, …...

编程日记 2025/9/7 12:20:28

怎么让一台云IPPBX实现多家酒店相同分机号码一起使用

下面用到的IPPBX是我们二次开发后的成品，支持各种云服务器一键安装，已经写好了一键安装包，自动识别系统环境，安装教程这里就不再陈述了！ 前言需求今天又遇到了一个客户咨询，关于部署一台云IPPBX&#xf…...

编程日记 2025/9/8 0:18:47

qt tcpsocket编程遇到的并发问题

1. 单个socket中接收消息的方法要使用局部变量而非全局，避免消息频发时产生脏数据优化后的关键代码 recieveInfo() 方法通过返回内部处理后的 msg 进行传递if (data.indexOf("0103") -1) { 这里增加了判断, 对数据（非注册和心跳&#xff0…...

编程日记 2025/9/3 8:55:55

U盘实现——BOT 常用命令

文章目录 U盘实现——BOT 常用命令命令格式CBWCSW数据传输条件命令传输数据传输状态传输命令汇总INQUIRY Command:12h数据格式抓包READ FORMAT CAPACITIES Command: 23h数据格式抓包READ CAPACITY Command: 25h数据格式抓包TEST UNIT READY Command: 00h数据格式抓包WRITE(10) …...

编程日记 2025/9/3 7:53:56

JavaScript DOM 节点操作

目录一、DOM 节点节点类型（Node Types） 二、查找节点 1.查找父节点 1. parentNode 2. parentElement 2.查找子节点 1. childNodes 2. children 3. firstChild / lastChild 4. firstElementChild / lastElementChild 3.查找兄弟节点 1. pre…...

编程日记 2025/9/8 0:11:24

JDBC常用的接口

一、什么是JDBC JDBC是Java语言连接数据库的接口规范。二、JDBC的体系 1、Java官方提供一个操作数据库的抽象接口抽象接口有很多的接口和抽象类。例如：Driver、Connection、Statement。 2、各个数据库厂商提供各自的Java实现类需要各自实现具体的细节。例如&am…...

编程日记 2025/8/29 0:30:25

【DLI】Generative AI with Diffusion Models通关秘籍

Generative AI with Diffusion Models，加载时间在20分钟左右，耐心等待。 6.2TODO 这里是在设置扩散模型的参数，代码里的FIXME部分需要根据上下文进行替换。以下是各个FIXME的替换说明： 1.a_bar 是 a 的累积乘积，在 …...

编程日记 2025/9/8 5:36:38

TP6图片操作 Image::open 调用-＞save(）方法时候报错Type is not supported

错误提示： { "code": 0, "msg": "Type is not supported", "data": { "code": 0, "line": 50, "file": "/www/wwwroot/ytems/vendor/topthink/framework/src/think…...

编程日记 2025/9/4 9:23:04

11_常用函数

文章目录一、概述二、字符函数2.1、获取字符串所占字节数2.2、获取字符个数2.3、拼接字符串2.4、大小写转换2.5、获取子串2.6、获取子串第一次出现的索引2.7、去除字符串前后子字符串2.7.1、去掉左侧空格2.7.2、去掉右侧空格 2.8、左右填充2.9、字符串替换三、数学函数3.1、四…...

编程日记 2025/9/3 18:15:03

《inZOI（云族裔）》50+MOD整合包

载具 RebelCore - 年龄和时间 mod启动器优化补丁去除雾气坦克模型菜单前置跳过启动更好性能等共计50MOD整合在游戏的世界里，追求更丰富、更优质的体验是玩家们永恒的主题。RebelCore 这款游戏通过精心打造的 50MOD 整合，为玩家带来了前所未有的…...

编程日记 2025/9/6 22:27:30

【技术报告】GPT-4o 原生图像生成的应用与分析

【技术报告】GPT-4o 原生图像生成的应用与分析 1. GPT-4o 原生图像生成简介1.1 文本渲染能力1.2 多轮对话迭代1.3 指令遵循能力1.4 上下文学习能力1.5 跨模态知识调用1.6 逼真画质与多元风格1.7 局限性与安全性 2. GPT-4o 技术报告2.1 引言2.2 安全挑战、评估与缓解措施2.2.1 安…...

编程日记 2025/9/3 9:07:36

拼多多延迟发货解答2

三、延迟发货处理标准延迟发货极大地影响了消费者的购物体验，平台对延迟发货行为也有相应的处理标准，因此各位商家一定不要以为延迟发货是小事儿。延迟发货处理标准具体可查看《拼多多发货规则》第3条。商家发生延迟发货的，拼多多平台有权…...

编程日记 2025/9/6 5:39:02

RTOS基础 -- NXP M4小核的RPMsg-lite与端点机制回顾

一、RPMsg-lite与端点机制回顾在RPMsg协议框架中： Endpoint（端点） 是一个逻辑通信端口，由本地地址（local addr）、远程地址（remote addr）和回调函数组成。每个消息都会发送到特定的…...

编程日记 2025/9/4 10:41:23

25.4.3学习总结【Java】

又是一道错题： 1. 班级活动https://www.lanqiao.cn/problems/17153/learning/?page1&first_category_id1&sortdifficulty&asc1&second_category_id3 问题描述小明的老师准备组织一次班级活动。班上一共有 n 名 (n 为偶数) 同学，老师…...

编程日记 2025/9/6 21:17:22

市场交易策略优化与波动管理

市场交易策略优化与波动管理在市场交易中，策略的优化和波动的管理至关重要。市场价格的变化受多种因素影响，交易者需要根据市场环境动态调整策略，以提高交易的稳定性，并有效规避市场风险。一、市场交易策略的优化方法趋势交易策…...

编程日记 2025/9/6 14:57:17

TypeScript 元数据操作 API 及示例

TypeScript 元数据操作 API 及示例 1. 配置环境安装依赖 npm install reflect-metadatatsconfig.json 配置 {"compilerOptions": {"experimentalDecorators": true,"emitDecoratorMetadata": true,"target": "ES6"} }2…...

编程日记 2025/9/5 4:04:22

蓝桥杯刷题记录【并查集001】（2024）

主要内容：并查集并查集并查集的题目感觉大部分都是模板题，上板子！！ class UnionFind:def __init__(self, n):self.pa list(range(n))self.size [1]*n self.cnt ndef find(self, x):if self.pa[x] ! x:self.pa[x] self.fi…...

编程日记 2025/9/8 11:10:44

搜广推校招面经六十六

高德推荐算法一、介绍Transformer中的位置编码（Positional Encoding） 在 Transformer 结构中，由于模型没有内置的序列信息（不像 RNN 那样有时间步的顺序依赖），需要通过**位置编码（Positional…...

编程日记 2025/9/5 7:48:29

Java高频面试题2：集合框架

一、集合框架概述 1. 常见的集合框架有哪些？ Collection：存储单个元素的集合。 List（有序、可重复）：ArrayList（动态数组）、LinkedList（双向链表）。Set（无序…...

编程日记 2025/9/4 13:34:55

06-公寓租赁项目-后台管理-公寓管理篇

尚庭公寓项目/公寓管理模块 https://www.yuque.com/pkqzyh/qg2yge/5ba67653b51379d18df61b9c14c3e946 一、属性管理属性管理页面包含公寓和房间各种可选的属性信息，其中包括房间的可选支付方式、房间的可选租期、房间的配套、公寓的配套等等。其所需接口如下 1.1…...

编程日记 2025/9/6 1:29:20

目前主流OCR/语义理解/ASR

OCR 基于多篇专业评测的结果，以下是目前免费开源OCR工具的推荐排名（侧重中文场景）： 1. RapidOCR 优势：基于PaddleOCR优化，在印刷中文、自然场景文字识别中综合评分第一，支持180度旋转和低对比…...

编程日记 2025/8/30 17:48:21

Selenium 元素定位方法详解

Selenium 提供了多种元素定位方式，掌握这些方法是进行 Web 自动化测试的基础。以下是主要的元素定位方法及其使用示例： 1. 基本定位方法 1.1 通过 ID 定位 element driver.find_element(By.ID, "element_id") 1.2 通过 Name 定位 element …...

编程日记 2025/9/3 1:33:36

fastGPT—前端开发获取api密钥调用机器人对话接口（HTML实现）

官网文档链接：OpenAPI 介绍 | FastGPT 首先按照文档说明创建api密钥 <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><meta name"viewport" content"widthdevice-width, initial-sca…...

编程日记 2025/9/4 19:13:07

c语言数据结构--------拓扑排序和逆拓扑排序(Kahn算法和DFS算法实现)

#include <stdio.h> #include <string.h> #include <stdbool.h> #include <stdlib.h>//使用卡恩算法(Kahn)和深度优先算法(DFS)实现//拓扑排序和逆拓扑排序//拓扑排序和逆拓扑排序顶点顺序相反//图，邻接矩阵存储 #define MaxVertexNum 100 …...

编程日记 2025/8/29 2:03:48

日期类的实现

本文运用c类和对象中的构造函数， 析构函数 ，拷贝构造函数 ， 赋值运算符重载等为大家模拟实现日期类的操作 #define _CRT_SECURE_NO_WARNINGS 1 #include"date.h" void Date:: showinfo() {cout << _year << "年&…...

编程日记 2025/9/3 7:08:14

3dgs通俗讲解

3d gaussian splatting：基于splatting和机器学习的三维重建方法。特点： 无深度学习简单的机器学习大量的CG知识复杂的线性代数对GPU的高性能编程一、什么是splatting 1、选择“雪球”； 为什么使用核（雪球） 各向…...

编程日记 2025/9/5 16:30:05

源码分析之Leaflet比例尺控件Control.Scale实现原理

概述 Control.Scale 是一个用于显示地图比例尺的控件，是 Leaflet 中实现比例尺控件的核心逻辑，用于在地图上动态显示公制（米/千米）和英制（英尺/英里）的比例尺。源码分析源码实现 Control.Scale的源码…...

编程日记 2025/9/6 19:28:47

【无标题 langsmith

【GPT入门】第32课 langsmith介绍与实战 1.lang smith作用2.lang smith配置方法3. 上手第一个lang smith3.1 可运行代码3.2 lang smith 官网，个人项目下 1.lang smith作用 LangSmith是由LangChain开发的一个平台，主要用于构建生产级LLM应用程序&#xf…...

编程日记 2025/8/29 2:03:38

智能建造新范式：装配式建筑 4.0 的数字化进阶

在全球数字化与可持续发展的浪潮中，建筑业正经历着第四次工业革命的深刻变革。装配式建筑4.0的出现，标志着建筑行业从传统的“钢筋水泥时代”迈向“数据驱动时代”，其核心在于通过技术融合重构建筑全生命周期的生产方式，实现从设计…...

编程日记 2025/9/2 20:42:00

从标准输入中读取所有内容sys.stdin.read()

sys.stdin.read().strip() 用于从标准输入中读取所有内容并去除首尾的空白字符。 1. sys.stdin.read() 作用：从标准输入流中读取所有内容，直到遇到文件结束符（EOF）。在命令行中，EOF 可以通过 CtrlD（Linux…...

编程日记 2025/9/4 1:26:28

网络：华为数通HCIA学习：静态路由基础

文章目录前言静态路由基础静态路由应用场景静态路由配置静态路由在串行网络的配置静态路由在以太网中的配置负载分担配置验证路由备份（浮动静态路由）配置验证缺省路由配置验证总结华为HCIA 基础实验－静态路由 & eNSP静态路由基础…...

编程日记 2025/9/3 0:42:57

DAY 35 leetcode 202--哈希表.快乐数

题号202 编写一个算法来判断一个数 n 是不是快乐数。「快乐数」定义为： 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。然后重复这个过程直到这个数变为 1，也可能是无限循环但始终变不到 1。如果这个过程结果为 1&a…...

编程日记 2025/9/6 2:34:35

Linux Command nmap 网络扫描

tags: 网络文章目录简介原理端口状态选项基本扫描发现扫描禁用DNS名称解析无ping扫描端口扫描版本检测防火墙规避技术故障排除和调试NMAP 脚本简介 Nmap（“ Network Mapper ”）是一个用于网络探索和安全审计的开源工具。它旨在快速扫描大型网络&…...

编程日记 2025/9/4 6:27:32

根据源码分析vue中nextTick的实现原理

根据源码分析vue中nextTick的实现原理一. ‌核心变量定义‌‌二. 异步策略选择（降级处理）‌1. 微任务优先‌2. 降级到 MutationObserver‌3. 降级到宏任务‌ 三、回调执行逻辑‌四、 ‌nextTick 函数实现‌五、 ‌与 Vue 更新流程的结合‌六‌、关键设计…...

编程日记 2025/9/8 7:18:22

Linux内核TCP/IP协议栈中的设计模式：从面向对象到系统级软件的跨界实践

引言设计模式（Design Patterns）自GoF（Gang of Four）在1994年提出以来，已成为软件工程领域的核心概念。尽管其经典定义基于面向对象编程（OOP），但设计模式的本质是解决复杂问题的经验总结，而非局限于特定编程范式。本文以Linux内核的TCP/IP协议栈为例，探讨设计模式在…...

编程日记 2025/9/7 8:14:09

风云可测：华为AI天气大模型将暴雨预测误差缩至3公里内

华为云正式发布全球首个气象专用人工智能大模型"盘古气象"，实现台风路径24小时预测误差<30公里、暴雨落区72小时精度91%，较传统数值预报效率提升10000倍。本文基于对西北太平洋10个台风回溯测试、全国2360个气象站验证数据，解析…...

编程日记 2025/8/31 16:02:22

DeepSeek-R1 面试题汇总

Deepseek-r1 面试宝典原文地址：https://articles.zsxq.com/id_91kirfu15qxw.html DeepSeek-R1 面试题汇总 DeepSeek-R1 面试题汇总 GRPO（Group Relative Policy Optimization）常见面试题汇总篇 DeepSeek-R1 DeepSeek-R1-Zero 常见面试题汇总…...

编程日记 2025/9/4 3:57:54