package org.hongjn.algorithm.sort;
import java.util.Arrays;
/**
* 基数排序Java实现
* @date 2011-10-19
*/
public class RadixSort {
/**
*
* @param data 待排序数组
* @param digitNum 数组中元素的位次
*/
public static int[] sort(int[] data) {
// 取得数组中最大的元素
int maxElement = 0;
for (int element : data) {
if (element > maxElement) {
maxElement = element;
}
}
String maxElementStr = String.valueOf(maxElement);
// 计算数组中最大元素的位数
int digitNum = maxElementStr.length();
// 从最低位开始,按照其基数radix进行排序
for (int i = 1; i <= digitNum; i++) {
// 根据基数的范围构建临时数组
int[] tmp = new int[10]; // 十进制数,基数0-9共十个
for (int element : data) {
int radix = getRadix(element, i); // 取得元素第i位上的基数
++tmp[radix]; // 对于基数radix相同的,在数组tmp中累积相加
}
// 此处,计算数组tmp中小于等于基数j的个数
for (int j = 1; j < tmp.length; j++) {
tmp[j] = tmp[j] + tmp[j - 1];
}
int[] result = new int[data.length]; // 存储每次排序的结果
// 遍历数组,排序
for (int k = data.length - 1; k >= 0; k--) {
// 对于遍历到的每个元素,取得第k位的基数radix
int radix = getRadix(data[k], i);
// 根据基数在tmp数组中的位置,确定该元素在数组result中的位置
result[--tmp[radix]] = data[k];
}
// 将result的数据拷贝回data,继续循环
data = Arrays.copyOf(result, result.length);
}
return data;
}
// 求得数组num的第d位的基数
private static int getRadix(int num, int d) {
return (int) (num / Math.pow(10, d - 1)) % 10;
}
}
分享到:
相关推荐
排序算法中的基数排序,更重要的是会算时间复杂度,基数排序可以说是以计数排序位基础的,只不过变成了一位一位来或者一个字节一个字节来,每位或者每个字节都过了一遍,则排序完毕。很简单的程序,在code::block IDE...
主要介绍了Java基数排序radix sort原理及用法解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友可以参考下
经典排序算法 – 基数排序Radix sort 原理类似桶排序,这里总是需要10个桶,多次使用 首先以个位数的值进行装桶,即个位数为1则放入1号桶,为9则放入9号桶,暂时忽视十位数 例如 待排序数组[62,14,59,88,16]简单点五个...
void radix_sort(int A[],int B[],int length,int d) { int i; for (i=1;i;i++) { get_k(A,B,i,length,d); insert_sort(B,A,length); printf("\n\n第%d位排序完成的结果:\n\n",i); print_A(A,length); ...
Radix Sort (基数排序)排序算法
基数排序的实现 算法是《数据结构(c语言版)》上的,自己写了实现 c++写的
基数排序的原理和程序 Radix Sort Tutorial
经典排序算法 - 基数排序Radix sort 经典排序算法 - 鸽巢排序Pigeonhole sort 经典排序算法 - 归并排序Merge sort 经典排序算法 - 冒泡排序Bubble sort 经典排序算法 - 选择排序Selection sort 经典排序算法 - ...
基数排序是一种非比较排序算法,其基本思想是将整数按位数切割成不同的数字,然后按每个位数分别进行排序。
基数排序(radix sort), 的c++模板实现
基数排序(radix sort)属于“分配式排序”(distribution sort),又称“桶子法”(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些“桶”中,藉以达到排序的作用,基数排序...
基数排序(radix sort)又称桶排序(bucket sort),相对于常见的比较排序,基数排序是一种分配式排序,需要将关键字拆分成数字位。并且按照数字位的值对数据项进行排序,这种方法不需要进行比较操作。 为了尽可能少的...
这边所要介绍的「基数排序法」(radix sort)则是属于「分配式排序」(distribution sort),基数排序法又称「桶子法」(bucket sort)或bin sort,顾名思义,它是透过键值的部份资讯,将要排序的元素分配至某些「桶...
关于在图形处理单元(GPU)上进行排序算法研究的论文,标题为《Onesweep: A Faster Least Significant Digit Radix Sort for GPUs》,作者是Andy Adinets和Duane Merrill,来自NVIDIA Corporation。 摘要: 文中...
排序算法 - 快速排序(Insert Sort) - 希尔排序(Shell Sort) - 冒泡排序(Bubble Sort) - 快速排序(Quick Sort) - 选择排序(Selection Sort) - 堆排序(Heap Sort) - 归并排序(Merge Sort) ...- 基数排序(Radix Sort)
基数排序的排序工作在线性时间之内就可以完成,速度非常之快,这里给出了基于计数排序和桶排序的两种类型的基数排序算法
基数排序和桶排序、计数排序共同是三种最常用的线性排序算法,这里我们就来深入解析Radix Sort基数排序算法思想及C语言实现示例,需要的朋友可以参考下
基数排序(Radix sort)是一种非比较型整数排序算法,其原理是将整数按位数切割成不同的数字,然后按每个位数分别比较。由于整数也可以表达字符串(比如名字或日期)和特定格式的浮点数,所以基数排序也不是只能使用于...