Java实现基数排序

简介: Java实现基数排序

基数排序和计数排序一样无需进行比较和交换,和桶排序一样利用分布和收集两种基本操作进行排序。基数排序是把每一个元素拆成多个关键字,一个关键字可以在每一个元素上同等的位置进行计数排序,一个元素拆成多个关键字可以看作是要进行几轮分桶,以一个元素最长的长度为准。

基数排序可以看成多(单)关键字的排序,可以想象成桶排序那样分桶排序,也可以像计数排序那样归约化分治。

基数排序的思想是将待排序序列中的每组关键字进行桶排序。例如整数序列[103, 9, 1,7,11,15, 25, 201, 209, 107, 5]上每个位、十位和百位上的数字看成是一个关键字。

源码

package com;
import java.util.Arrays;
import java.util.Scanner;
public class Main {
  public static void main(String[] args) {
    Scanner s=new Scanner (System.in);
    int n=s.nextInt();
    int [] a=new int [n];
    for(int i=0;i<n;i++)
      a[i]=(int)(Math.random()*100);
    radixsort(a);
    System.out.println(Arrays.toString(a));
  }
  public static void radixsort (int[] a) {
    int max=a[0];
    for(int i=1;i<a.length;i++) {
      if(a[i]>max)
        max=a[i];
    }
    int maxLength=(max+"").length();
    int [][] bucket=new int [10][a.length];
    int [] bucketCount=new int [10];
    for(int k=0,n=1;k<maxLength;k++,n*=10) {
      for(int i=0;i<a.length;i++) {
        int dight=a[i]/n%10;
        bucket[dight][bucketCount[dight]]=a[i];
        bucketCount[dight]++;
      }
      int index=0;
      for(int i=0;i<10;i++) {
        if(bucketCount[i]!=0) {
          for(int j=0;j<bucketCount[i];j++) {
            a[index]=bucket[i][j];
            index++;
          }
        }
        bucketCount[i]=0;
      }
    }
  } 
}

以上代码仅供参考


目录
相关文章
|
7月前
|
Java
基数排序(java)
基数排序(java)
|
搜索推荐 算法 Java
【算法】基数排序的原理与Java实现
基数排序(Radix Sort)是一种非比较性的排序算法,它根据元素的位数逐位进行排序。基数排序的核心思想是将待排序的元素按照低位到高位的顺序进行排序,每一位都使用稳定的排序算法(通常是计数排序或桶排序)。通过多次按位排序,最终可以得到有序的结果
124 0
|
搜索推荐 Java
深入了解基数排序:原理、性能分析与 Java 实现
基数排序(Radix Sort)是一种非比较性排序算法,它根据元素的每个位上的值来进行排序。基数排序适用于整数或字符串等数据类型的排序。
186 2
深入了解基数排序:原理、性能分析与 Java 实现
|
算法 Java
java实现基数排序
java实现基数排序
51 0
|
算法 搜索推荐 Java
经典十大排序算法(含升序降序,基数排序含负数排序)【Java版完整代码】【建议收藏系列】
经典十大排序算法(含升序降序,基数排序含负数排序)【Java版完整代码】【建议收藏系列】
经典十大排序算法(含升序降序,基数排序含负数排序)【Java版完整代码】【建议收藏系列】
|
存储 人工智能 算法
八大排序算法Java实现(下)-快排、归排、基数排序
八大排序算法Java实现(下)-快排、归排、基数排序
168 0
八大排序算法Java实现(下)-快排、归排、基数排序
|
15天前
|
监控 Java
java异步判断线程池所有任务是否执行完
通过上述步骤,您可以在Java中实现异步判断线程池所有任务是否执行完毕。这种方法使用了 `CompletionService`来监控任务的完成情况,并通过一个独立线程异步检查所有任务的执行状态。这种设计不仅简洁高效,还能确保在大量任务处理时程序的稳定性和可维护性。希望本文能为您的开发工作提供实用的指导和帮助。
72 17
|
26天前
|
Java
Java—多线程实现生产消费者
本文介绍了多线程实现生产消费者模式的三个版本。Version1包含四个类:`Producer`(生产者)、`Consumer`(消费者)、`Resource`(公共资源)和`TestMain`(测试类)。通过`synchronized`和`wait/notify`机制控制线程同步,但存在多个生产者或消费者时可能出现多次生产和消费的问题。 Version2将`if`改为`while`,解决了多次生产和消费的问题,但仍可能因`notify()`随机唤醒线程而导致死锁。因此,引入了`notifyAll()`来唤醒所有等待线程,但这会带来性能问题。
Java—多线程实现生产消费者
|
11天前
|
缓存 安全 算法
Java 多线程 面试题
Java 多线程 相关基础面试题
|
28天前
|
安全 Java Kotlin
Java多线程——synchronized、volatile 保障可见性
Java多线程中,`synchronized` 和 `volatile` 关键字用于保障可见性。`synchronized` 保证原子性、可见性和有序性,通过锁机制确保线程安全;`volatile` 仅保证可见性和有序性,不保证原子性。代码示例展示了如何使用 `synchronized` 和 `volatile` 解决主线程无法感知子线程修改共享变量的问题。总结:`volatile` 确保不同线程对共享变量操作的可见性,使一个线程修改后,其他线程能立即看到最新值。
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等