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

php 实现基数排序

1、基数排序介绍

基数排序是一种基于数字每一位进行排序的算法。它从最低位开始,依次对每一位进行排序,直到最高位。对于整数,从个位开始,将所有数字按照个位数字放入相应的“桶”中,然后按桶的顺序重新收集数据;接着对十位进行同样的操作,以此类推,直到处理完最高位。例如,对于数组[123, 456, 789, 111, 222],先按个位数字排序,再按十位数字排序,最后按百位数字排序,从而得到有序数组。

2、PHP代码实现(支持处理负数):

function radixSort($arr) {$n = count($arr);if ($n <= 1) return $arr;// 处理负数:转换为非负整数$minVal = min($arr);$offset = ($minVal < 0) ? -$minVal : 0;foreach ($arr as &$num) {$num += $offset;}// 获取最大值确定位数$maxVal = max($arr);$exp = 1; // 从个位开始while (floor($maxVal / $exp) > 0) {$arr = countingSort($arr, $exp);$exp *= 10; // 处理十位、百位...}// 恢复原始数值(减去偏移量)if ($offset != 0) {foreach ($arr as &$num) {$num -= $offset;}}return $arr;
}function countingSort($arr, $exp) {$n = count($arr);$output = array_fill(0, $n, 0);$count = array_fill(0, 10, 0);// 统计当前位的出现次数foreach ($arr as $num) {$digit = floor(($num / $exp) % 10);$count[$digit]++;}// 计算累加位置for ($i = 1; $i < 10; $i++) {$count[$i] += $count[$i - 1];}// 反向填充保证稳定性for ($i = $n - 1; $i >= 0; $i--) {$digit = floor(($arr[$i] / $exp) % 10);$output[$count[$digit] - 1] = $arr[$i];$count[$digit]--;}return $output;
}// 示例测试
$testCases = [[-5, 10, -3, 2, 0],   // 含负数[170, 45, 75, 90, 802, 24, 2, 66],[0, 0, 1, 1, 0],      // 重复元素[10000, 999, 100, 10, 1],
];foreach ($testCases as $nums) {$sorted = radixSort($nums);echo "排序前: " . implode(", ", $nums) . "\n";echo "排序后: " . implode(", ", $sorted) . "\n\n";
}

3、执行结果示例

排序前: -5, 10, -3, 2, 0
排序后: -5, -3, 0, 2, 10

排序前: 170, 45, 75, 90, 802, 24, 2, 66
排序后: 2, 24, 45, 66, 75, 90, 170, 802

排序前: 0, 0, 1, 1, 0
排序后: 0, 0, 0, 1, 1

排序前: 10000, 999, 100, 10, 1
排序后: 1, 10, 100, 999, 10000

4、代码解释

1. 处理负数
  • 找到最小值 $minVal,计算偏移量 $offset
  • 将所有元素加上 $offset,确保数组中的值非负。
2. 按位排序(核心逻辑)
  • 确定最大位数:根据 $maxVal 计算需要处理的位数,例如 802 需要处理到百位(exp=100)。
  • 计数排序:对当前位(个位、十位、百位等)进行稳定排序:
    • 统计频率:统计每个数字(0-9)出现的次数。
    • 计算累加位置:将 $count 数组转换为每个数字的结束索引。
    • 反向填充:从原数组末尾遍历,按当前位数字放入 $output 数组的正确位置。
3. 恢复原始值
  • 排序完成后,如果存在负数,将每个元素减去 $offset,恢复原始数值。

5、复杂度分析

  • 时间复杂度:O(d*(n + k)),其中:
    • d 是最大位数,k 是基数(十进制为10)。
    • 每个位数需要进行一次计数排序(O(n + k))。
  • 空间复杂度:O(n + k),用于计数数组 $count 和输出数组 $output

6、适用场景

  • 整数或定长字符串排序:如手机号、身份证号的排序。
  • 数据范围大但位数少:例如对 10^6 个 3 位数排序。
  • 需要稳定排序:如对多关键字排序(先按第二位排序,再按第一位)。

http://www.xdnf.cn/news/9129.html

相关文章:

  • 编程规范Summary
  • ASP.NET Web Forms框架识别
  • 【论文精读】2024 arXiv --VEnhancer现实世界视频超分辨率(RealWorld VSR)
  • 【数据结构】——二叉树堆(下)
  • Windows系统下 NVM 安装 Node.js 及版本切换实战指南
  • 什么是 WPF 技术?什么是 WPF 样式?下载、安装、配置、基本语法简介教程
  • 云效流水线Flow使用记录
  • 论文阅读笔记——Step1X-Edit: A Practical Framework for General Image Editing
  • Oracle 正则表达式匹配(Oracle 11g)
  • Rockey Linux 安装ffmpeg
  • 抖音不获取位置会显示ip属地吗?全面解析
  • AWS EC2 实例告警的创建与删除
  • some面试题2
  • 15.进程间通信(一)
  • Linux 527 重定向 2>1 rsync定时同步(未完)
  • python打卡day38
  • Django【应用 02】第一个Django应用开发流程图
  • WPF【11_1】WPF实战-重构与美化(Entity Framework)
  • 分布式常见概念
  • 25.5.27学习总结
  • pod创建和控制
  • day38 python Dataset和Dataloader
  • OpenCV CUDA模块图像处理------颜色空间处理之GPU 上交换图像的通道顺序函数swapChannels()
  • Wan2.1 图生视频模型内部协作流程
  • 02.【Qt开发】Qt Creator介绍及新建项目流程
  • Python打卡 DAY 38
  • 华为高斯数据库(GaussDB)深度解析:国产分布式数据库的旗舰之作
  • 局域协作中的前端调试:WebDebugX 在本地多端调试中的实践
  • CPU服务器的主要功能有哪些?
  • 高防CDN如何解决网站访问卡顿与崩溃问题?