一、
基数排序即分配排序,以低位优先(LSD)为例,
1,先取出待排数的个位数(0-9),
2,将其放到对应标号为0-9的桶(每个桶中数都是线性对列)中,
3,再取十位,百位,千位,重复2步骤
进行一次分配后,从桶中取数据数,需按顺序取,至多分配n次(n为最大数的位数)
二、
import java.util.ArrayList;
class radixSort
{
public static void radixSort(int[] a){
//从最大的数max分析出需要分配time次
int max=a[0],time=0;
for(int i=1;i<a.length;i++){
if(a[i]>max){
max=a[i];
}
}
while(max>0){
max=max/10;
time++;
}
//构造标号为0-9的桶子
ArrayList[] assign=new ArrayList[10];
for(int i=0;i<10;i++){
assign[i]=new ArrayList<Integer>();
}
//开始分配
int bitNum=0;
for(int i=0;i<time;i++){
//第i次分配
for(int j=0;j<a.length;j++){
bitNum=(a[j]/(int)Math.pow(10, i))%10;
assign[bitNum].add(bitNum);
}
//从桶子中按序拿出数据
int k=0;
ArrayList temp;
for(int m=0;m<10;m++){
temp=assign[m];
for(int n=0;n<temp.size();n++){
a[k++]=(int)temp.get(n);
}
}
}
}
public static void main(String args[]){
int[] a={4,3,6,1,2,5,2,2,2,2,0,0,3,1,9,9,9};
radixSort(a);
for(int i=0;i<a.length;i++){
System.out.print(a[i]+" ");
}
}
}
分享到:
相关推荐
基数排序/桶排序 *统计将数组中的数字分配到桶中后,各个桶中的数字个数 *数组中每个数的每一位数根据大小分配到对应大小为0~9的桶 *将各个桶中的数字个数,转化成各个桶中最后一个数字的下标索引
算法导论之基数排序,桶排序。基数排序是利用在各个位上进行计数排序,是一种线性排序
基数排序(radix sort)又称桶排序(bucket sort),相对于常见的比较排序,基数排序是一种分配式排序,需要将关键字拆分成数字位。并且按照数字位的值对数据项进行排序,这种方法不需要进行比较操作。 为了尽可能少的...
Java排序算法:插入,冒泡,选择,Shell,快速排序,归并排序,堆排序,桶式排序,基数排序
基数排序法又称「桶子法」(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些「桶」中,藉以达到排序的作用,基数排序法是属于稳定性的排序,其时间复杂度为O (nlog(r)m),...
各种排序算法的实现函数:包括冒泡排序、选择排序、插入排序、希尔排序、归并排序、快速排序、堆排序、计数排序、桶排序、基数排序。 查找最大最小值函数 findMinMax:在给定数组中查找最大值和最小值。 计算平均值...
在这份文档中,我用C语言实现了排序算法的多种方法,包括插入排序、选择排序、冒泡排序、希尔排序、归并排序、快速排序、桶排序和基数排序。这些算法可以帮助我们对数据进行有效的排序和整理,以便更好地处理和分析...
基数排序从最低位开始,依次对每一位上的数字进行排序,并使用桶排序或计数排序作为子程序。基数排序具有稳定性,适用于整数排序,并且当整数的位数不多时,其时间复杂度是非常高效的。然而,基数排序也有其局限性,...
使用C语言,模拟了箱排序和基数排序算法.希望可以大家一起共勉. 桶排序:https://blog.csdn.net/forwardyzk/article/details/102935430 基数排序:https://blog.csdn.net/forwardyzk/article/details/107723795
包含冒泡排序、快速排序、插入排序、基数排序以及 速度快于 快速排序的 桶排序。欢迎大家学习交流。
基数排序是一种非比较型整数排序算法,通过按数字的每一位...然而,基数排序需要额外的存储空间来模拟桶,空间复杂度较高。以下是使用C++实现的基数排序算法,通过模拟桶的分配和收集过程,实现对非负整数序列的排序。
直接插入排序 直接插入排序(Straight Insertion Sort)是一种简单且古老的排序算法,其基本思想是将一个记录插入到已经排好序的有序表中,从而得到一个新的、记录数增1的有序表。12 直接插入排序的算法过程如下...
然而,基数排序需要额外的存储空间来存放桶,因此空间复杂度较高。在Java中,基数排序的实现通常包括确定最大数的位数、对每一位进行排序、分配和收集数字等步骤。此外,为了处理负数或浮点数,可能需要在排序前进行...
基数排序的排序工作在线性时间之内就可以完成,速度非常之快,这里给出了基于计数排序和桶排序的两种类型的基数排序算法
包含算法导论/数据结构中各种常用的排序算法:快速排序 冒泡排序 堆排序 选择排序 归并排序 插入排序 二分插入排序 希尔排序 计数排序 基数排序 桶式排序
数据结构之排序算法 包含目前所有排序方法: 1 快速排序 2 冒泡排序 3 堆排序 4 希尔排序 5 直接插入排序 6 直接选择排序 7 基数排序 8 箱、桶排序 9 归并排序
快速排序
一、桶排序: 排序一个数组[5,3,6,1,2,7,5,10] 值都在1-10之间,建立10个桶: [0 0 0 0 0 0 0 0 0 0] 桶 [1 2 3 4 5 6 7 8 9 10] 桶代表的值 遍历数组,第一个数字5,第五个桶加1 [0 0 0 0 1 0 0 0 0 0] 第二个数字...