Java语言实现基数排序代码分享
算法思想：依次按个位、十位...来排序，每一个pos都有分配过程和收集过程，array[i][0]记录第i行数据的个数。
package sorting;
/**
* 基数排序
* 平均O(d(n+r)),最好O(d(n+r)),最坏O(d(n+r));空间复杂度O(n+r);稳定;较复杂
* d为位数,r为分配后链表的个数
* @author zeng
*
*/
public class RadixSort {
//pos=1表示个位，pos=2表示十位
public static int getNumInPos(int num, int pos) {
int tmp = 1;
for (int i = 0; i < pos - 1; i++) {
tmp *= 10;
}
return (num / tmp) % 10;
}
//求得最大位数d
public static int getMaxWeishu(int[] a) {
int max = a[0];
for (int i = 0; i < a.length; i++) {
if (a[i] > max)
max = a[i];
}
int tmp = 1, d = 1;
while (true) {
tmp *= 10;
if (max / tmp != 0) {
d++;
} else
break;
}
return d;
}
public static void radixSort(int[] a, int d) {
int[][] array = new int[10][a.length + 1];
for (int i = 0; i < 10; i++) {
array[i][0] = 0;
// array[i][0]记录第i行数据的个数
}
for (int pos = 1; pos <= d; pos++) {
for (int i = 0; i < a.length; i++) {
// 分配过程
int row = getNumInPos(a[i], pos);
int col = ++array[row][0];
array[row][col] = a[i];
}
for (int row = 0, i = 0; row < 10; row++) {
// 收集过程
for (int col = 1; col <= array[row][0]; col++) {
a[i++] = array[row][col];
}
array[row][0] = 0;
// 复位，下一个pos时还需使用
}
}
}
public static void main(String[] args) {
int[] a = { 49, 38, 65, 197, 76, 213, 27, 50 };
radixSort(a, getMaxWeishu(a));
for (int i : a)
System.out.print(i + " ");
}
}
关注一下运行结果：
总结
以上就是本文关于Java语言实现基数排序代码分享的全部内容，希望对大家有所帮助。感兴趣的朋友可以继续参阅本站其他Java相关专题，如有不足之处，欢迎留言指出。感谢朋友们对本站的支持！
相关推荐
-
Java实现按照大小写字母顺序排序的方法
本文实例讲述了Java实现按照大小写字母顺序排序的方法.分享给大家供大家参考,具体如下: 这里排序需要得到的结果按字母顺序.如:a-----z... import java.util.*; /** * 大小写字母的排序 * @author Administrator * */ public class z { //上边是按大写在后的进行排序 static Map<Character,Float> map=new HashMap<Character,Float>();//hashMa
-
Java编程实现直接插入排序代码示例
算法描述:对于给定的一个数组,初始时假设第一个记录自成一个有序序列,其余记录为无序序列.接着从第二个记录开始,按照记录的大小依次将当前处理的记录插入到其之前的有序序列中,直至最后一个记录插入到有序序列中为止. 直接插入排序Java实现教程 示例1 public class Insert { public static void main(String[] args) { int a[] = {9,3,28,6,34,7,10,27,1,5,8}; show(a); for (int i=1;i
-
Java排序算法之归并排序简单实现
算法描述:对于给定的一组记录,首先将每两个相邻的长度为1的子序列进行归并,得到 n/2(向上取整)个长度为2或1的有序子序列,再将其两两归并,反复执行此过程,直到得到一个有序序列. package sorting; /** * 归并排序 * 平均O(nlogn),最好O(nlogn),最坏O(nlogn);空间复杂度O(n);稳定;较复杂 * @author zeng * */ public class MergeSort { public static void merge(int[] a,
-
Java 堆排序实例(大顶堆、小顶堆)
堆排序(Heapsort)是指利用堆这种数据结构所设计的一种排序算法.堆积是一个近似完全二叉树的结构,并同时满足堆积的性质:即子结点的键值或索引总是小于(或者大于)它的父节点. 堆排序的平均时间复杂度为Ο(nlogn) . 算法步骤: 1. 创建一个堆H[0..n-1] 2. 把堆首(最大值)和堆尾互换 3. 把堆的尺寸缩小1,并调用shift_down(0),目的是把新的数组顶端数据调整到相应位置 4. 重复步骤2,直到堆的尺寸为1 堆: 堆实际上是一棵完全二叉树,其任何一非叶节点满足性质:
-
Java编程实现快速排序及优化代码详解
普通快速排序 找一个基准值base,然后一趟排序后让base左边的数都小于base,base右边的数都大于等于base.再分为两个子数组的排序.如此递归下去. public class QuickSort { public static <T extends Comparable<? super T>> void sort(T[] arr) { sort(arr, 0, arr.length - 1); } public static <T extends Comparabl
-
堆排序实例(Java数组实现)
堆排序:利用大根堆 数组全部入堆,再出堆从后向前插入回数组中,数组就从小到大有序了. public class MaxHeap<T extends Comparable<? super T>> { private T[] data; private int size; private int capacity; public MaxHeap(int capacity) { this.data = (T[]) new Comparable[capacity + 1]; size =
-
Java分治归并排序算法实例详解
本文实例讲述了Java分治归并排序算法.分享给大家供大家参考,具体如下: 1.分治法 许多有用的算法在结构上是递归的:为了解决一个给定的问题,算法一次或多次递归地调用其自身以解决紧密相关的若干子问题.这些算法典型地遵循分治法的思想:将原问题分解为几个规模较小但类似于原问题的子问题,递归地求解这些子问题,然后再合并这些子问题的解来建立原问题的解. 分治模式在每层递归时都有三个步骤: (1)分解原问题为若干子问题,这些子问题是原问题的规模较小的实例. (2)解决这些子问题,递归地求解各子问题.然而,
-
基数排序简介及Java语言实现
基本思想 基数排序(RadixSort)是在桶排序的基础上发展而来的,两种排序都是分配排序的高级实现.分配排序(DistributiveSort)的基本思想:排序过程无须比较关键字,而是通过"分配"和"收集"过程来实现排序.它们的时间复杂度可达到线性阶:O(n). 基数排序是一种稳定的排序算法,但有一定的局限性: 1.关键字可分解. 2.记录的关键字位数较少,如果密集更好 3.如果是数字时,最好是无符号的,否则将增加相应的映射复杂度,可先将其正负分开排序. 先来看一
-
Java语言实现基数排序代码分享
算法思想:依次按个位.十位...来排序,每一个pos都有分配过程和收集过程,array[i][0]记录第i行数据的个数. package sorting; /** * 基数排序 * 平均O(d(n+r)),最好O(d(n+r)),最坏O(d(n+r));空间复杂度O(n+r);稳定;较复杂 * d为位数,r为分配后链表的个数 * @author zeng * */ public class RadixSort { //pos=1表示个位,pos=2表示十位 public static int g
-
Java 常见排序算法代码分享
目录 1. 冒泡排序 2. 选择排序 3. 插入排序 4. 快速排序 5. 归并排序 6. 希尔排序 6.1 希尔-冒泡排序(慢) 6.2 希尔-插入排序(快) 7. 堆排序 8. 计数排序 9. 桶排序 10. 基数排序 11. 使用集合或 API 11.1 优先队列 11.2 Java API 汇总: 1. 冒泡排序 每轮循环确定最值: public void bubbleSort(int[] nums){ int temp; boolean isSort = false;
-
Java编程泛型限定代码分享
泛型 一般 出现在集合中,迭代器中 也会出现! 泛型 是为了 提高代码的 安全性. 泛型 确保数据类型的唯一性. 在我们常用的容器中, 越是单一越好处理啊! 泛型的限定: ? 是通配符 指代 任意类型 泛型的限定上限: <? extends E> 接受 E 或者 E 的子类型. 泛型的限定下限: <? super E> 接收 E 或者 E 的父类. 泛型的限定上限 (定义父类 填装子类 类型!) 下面我们看看具体代码示例 package newFeatures8; imp
-
Java反射机制实例代码分享
本文旨在对Java反射机制有一个全面的介绍,希望通过本文,大家会对Java反射的相关内容有一个全面的了解. 阅读本文之前,大家可先行参阅<重新理解Java泛型>. 前言 Java反射机制是一个非常强大的功能,在很多大型项目比如Spring, Mybatis都可以看见反射的身影.通过反射机制我们可以在运行期间获取对象的类型信息,利用这一特性我们可以实现工厂模式和代理模式等设计模式,同时也可以解决Java泛型擦除等令人苦恼的问题.本文我们就从实际应用的角度出发,来应用一下Java的反射机制. 反射
-
Java实现TFIDF算法代码分享
算法介绍 概念 TF-IDF(term frequency–inverse document frequency)是一种用于资讯检索与资讯探勘的常用加权技术.TF-IDF是一种统计方法,用以评估一字词对于一个文件集或一个语料库中的其中一份文件的重要程度.字词的重要性随着它在文件中出现的次数成正比增加,但同时会随着它在语料库中出现的频率成反比下降.TF-IDF加权的各种形式常被搜寻引擎应用,作为文件与用户查询之间相关程度的度量或评级.除了TF-IDF以外,因特网上的搜寻引擎还会使用基于连结分析的评
-
java语言中封装类代码示例
在面向对象程序设计方法中,封装(Encapsulation)是指一种将抽象性函式接口的实现细节部分包装'隐藏起来的方法.数据被保护在内部,隐藏内部实现细节,对外提供接口与外部交互. 使用封装的步骤 将类的所有属性使用关键字private去修饰,把它们变成私有的,不允许外部类直接访问 生成或者提供公共的setter/getter方法去操作这些被隐藏起来的属性 在类自己的 setter/getter方法中加入逻辑控制,以确保数据访问的有效性和安全性实例 让我们来看一个java封装类的例子: /* 文
-
java图片添加水印实例代码分享
本文为大家介绍了java图片添加水印实例代码,java实现水印还是非常方便的,水印可以是图片或者文字,具体内容如下 package michael.io.image; import java.awt.AlphaComposite; import java.awt.Graphics2D; import java.awt.Image; import java.awt.RenderingHints; import java.awt.image.BufferedImage; import java.io
-
java制作android 日历代码分享
代码很简单,就不多废话了 复制代码 代码如下: //读取日历事件 public static void getCalendarInfo(Activity activity,String tag){ String[] projection = new String[]{CalendarContract.Events._ID,CalendarContract.Events.TITLE}; ContentResolver cr = activity.getCon
-
java web验证码实现代码分享
验证码的作用:通常的登录或者注册系统时,都会要求用户输入验证码,以此区别用户行为和计算机程序行为,目的是有人防止恶意注册.暴力破解密码等. 实现验证码的思路:用 server 实现随机生成数字和字母组成图片的功能,用 jsp 页面实现显示验证码和用户输入验证码的功能,再用 server 类分别获取图片和用户输入的数据,判断两个数据是否一致. 代码实现 1.编写数字.英文随机生成的 server 类,源码: package com; import java.awt.Color; import j
-
javascript中实现兼容JAVA的hashCode算法代码分享
在java中一个hashCode算法,可以用来计算一个字符串的hash值,今天一个朋友突然问俺能不能在js中计算hashCode,要求和java的hashCode计算结果一样. 对于java的hashCode,以前到现在也一直没有了解过其算法,不过猜想应该也不会太难,于是现在java中写了这段代码进行测试: 运行结果:899755 按下Ctrl键点击hashCode方法名跟进去看了下其算法,发现是很简单的几句代码,如下所示: 复制代码 代码如下: public int hashCode() {