十大排序算法之——基数排序算法(Java实现)及思路讲解

news/2024/12/22 13:28:29/

基数排序(Radix Sort)是一种非比较型整数算法>排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表示字符串(如名字或日期)和特定格式的浮点数,基数排序并不是只能用于整数。这里是基数排序的Java实现,并尽量将解释和代码控制在1500字以内。

基数排序的基本思想

基数排序按照低位先排序,然后收集;再按照高位排序,然后再收集;依次类推,直到最高位。有时候有些属性是有优先级顺序的,先按低优先级排序,再按高优先级排序。最后的次序就是高优先级高的在前,高优先级相同的低优先级高的在前。

基数排序的Java实现

下面是一个简单的基数排序Java实现,假设我们排序的是非负整数:

java">import java.util.ArrayList;
import java.util.List;public class RadixSort {// 获取最大数的位数public static int getMaxDigit(int[] arr) {int maxVal = arr[0];for (int value : arr) {maxVal = Math.max(maxVal, value);}int digit = 0;while (maxVal != 0) {maxVal /= 10;digit++;}return digit;}// 基数排序函数public static void radixsort(int[] arr) {// 获取最大数的位数int m = getMaxDigit(arr);// 初始化桶List<List<Integer>> bucketList = new ArrayList<>();for (int i = 0; i < 10; i++) {bucketList.add(new ArrayList<>());}// 对每一位使用稳定的计数排序for (int exp = 1; exp <= m; exp *= 10) {// 将数据分配到桶中for (int i = 0; i < arr.length; i++) {int bucketIndex = (arr[i] / exp) % 10;bucketList.get(bucketIndex).add(arr[i]);}// 收集桶中的数据int index = 0;for (List<Integer> bucket : bucketList) {for (int value : bucket) {arr[index++] = value;}bucket.clear(); // 清空桶,为下一次分配做准备}}}public static void main(String[] args) {int[] arr = {170, 45, 75, 90, 802, 24, 2, 66};radixsort(arr);// 输出排序后的数组for (int num : arr) {System.out.print(num + " ");}}
}

代码解释

  1. getMaxDigit 方法用于获取数组中最大数的位数,这是为了确定我们需要进行多少次排序(即每一位都需要进行一次排序)。
  2. radixsort 方法是基数排序的主要实现。它首先初始化10个桶(因为我们处理的是十进制数),然后对于每一位(从最低位开始),将数组中的数分配到对应的桶中,然后再从桶中收集数到原数组。这个过程重复进行,直到最高位。
  3. main 方法中,我们创建了一个待排序的数组,并调用 radixsort 方法进行排序。最后,我们输出排序后的数组。

基数排序的特点

  • 基数排序是稳定的排序方法。
  • 基数排序的时间复杂度是O(d*(n+k)),其中d为位数,n是待排数据数量,k是数值范围的个数。
  • 对于一定的n,基数排序的时间复杂度为O(n)。
  • 基数排序的空间复杂度为O(n+k),其中n为待排序列个数,k为数值范围的个数。

基数排序适合用于数值不大,但是数量很多的场合,特别是当数值分布均匀的时候,其效果甚至可以与快速排序和归并排序相媲美。

希望这个简单的基数排序Java实现和解释能够满足您的需求。如果您需要更深入的分析或者对特定部分的解释,请随时告诉我。


http://www.ppmy.cn/news/1453345.html

相关文章

C语言:文件操作(下)

片头 嗨&#xff01;小伙伴们&#xff0c;在前2篇中&#xff0c;我们分别讲述了C语言&#xff1a;文件操作&#xff08;上&#xff09;和 C语言&#xff1a;文件操作&#xff08;中&#xff09;&#xff0c;今天我们将会学习文件操作&#xff08;下&#xff09;&#xff0c;准…

Arxml文件解析01- 自动驾驶Radar服务radar_svc.arxml

本文章是在Adaptive AutoSAR环境下,对Arxml文件解析的系列文章,这系列文章将带你了解Adaptive AutoSAR Arxml文件包含的元素及相应的含义。下文的xml代码是radar_svc.arxml。 <?xml version="1.0" encoding="UTF-8"?> <AUTOSAR xmlns="…

Java 码农失业,有没有其他出路?

本人知乎账号同公众号&#xff1a;老胡聊Java&#xff0c;欢迎留言并咨询 如果是本科学历&#xff0c;30岁失业&#xff0c;真不用慌&#xff0c;别盲目转行&#xff0c;也别盲目继续在小公司之间跳&#xff0c;可以找机会进大中公司。如果是35岁&#xff0c;本文给出的方法还应…

勒索病毒最新变种.kat6.l6st6r勒索病毒来袭,如何恢复受感染的数据?

导言&#xff1a; 在信息化社会的浪潮中&#xff0c;网络安全问题日益凸显&#xff0c;其中勒索病毒成为了一个令人头疼的难题。最近出现的.kat6.l6st6r勒索病毒&#xff0c;以其独特的攻击方式和恶劣的勒索行为&#xff0c;再次敲响了网络安全的警钟。为了有效应对这一新型威…

【小菜鸟之---Linux网络配置】

文章目录 1【子网和网关】2【网络连接模式】3【ifconfig-查看网络接口信息】3.1 查询网络接口信息3.2 ifconfig——设置网络接口参数【**设置网络参数的方式**】【**临时设置**】**【永久设置】** 4【hostname-主机信息】4.1 查看主机名4.2 主机名修改4.3 查看本机ip 5【route-…

是机遇?是未来?拥抱 AI Agent ,拥抱 AI 2.0时代~

✍️ 作者&#xff1a;哈哥撩编程&#xff08;视频号同名&#xff09; 博客专家全国博客之星第四名超级个体COC上海社区主理人特约讲师谷歌亚马逊演讲嘉宾科技博主极星会首批签约作者 &#x1f3c6; 推荐专栏&#xff1a; &#x1f3c5; 程序员&#xff1a;职场关键角色通识宝…

AD单通道/多通道

1.AD单通道&#xff08;单次转换&#xff0c;非扫描模式&#xff09; 1.1 接线图 1.2 AD.c #include "stm32f10x.h" // Device headervoid AD_Init(void) {RCC_APB2PeriphClockCmd(RCC_APB2Periph_GPIOA,ENABLE);//开启GPIOA时钟RCC_APB2PeriphCl…

基于51单片机的智能台灯proteus仿真设计( proteus仿真+程序+原理图+报告+讲解视频)

基于51单片机的红外光敏检测智能台灯控制系统仿真( proteus仿真程序原理图报告讲解视频&#xff09; 1.主要功能&#xff1a; 基于51单片机的红外检测光照检测智能台灯仿真设计 1、检测光照强度并显示在数码管上。 2、具备红外检测人体功能。 3、灯光控制模式分为自动模式…