8、 基数排序
以基数是10为例
① 根据数据项个位上的值,把所有的数据分为10组。
② 然后对这10组数据项重新排列:把所有关键字是以0结尾的数据排在最后面,然后是关键字结尾时1的数据项,照此顺序直到以9结尾的数据项。这个步骤被称为第一趟子排序。
③ 在第二趟子排序中,再次把所有的数据项分为10组,但是这一次是根据数据项十位上的值来分组。这次分组不能改变先前的排序顺序。也就是说,第二趟排序之后,从每一组数据项的内部来看,数据项的顺序保持不变;这趟排序必须是稳定。
④ 然后再把10组数据项重新合并,排在最前面的是十位上为0的数据项,然后是十位为1的数据项,如此排序到十位上为9的数据项
⑤ 对剩余位重复这个过程。如果某些数据项的位数少于其他数据项的,那么认为他们的最高位为0
public static int[] countSort(int[] a, int k) {
int[] b = new int[a.length];
int[] c = new int[10];
for (int i = 0; i < b.length; i++) {
b[i] = 0;
}
for (int i = 0; i < c.length; i++) {
c[i] = 0;
}
int s = 1;
for (int i = 0; i < k; i++) {
s = s * 10;
}
int temp1 = 0;
for (int i = 0; i < a.length; i++) {
temp1 = a[i] % s;
temp1 = temp1 * 10 / s;
c[temp1] = c[temp1] + 1;
}
for (int i = 1; i < c.length; i++) {
c[i] = c[i] + c[i - 1];
}
int temp2 = 0;
for (int i = a.length - 1; i >= 0; i--) {
temp1 = a[i];
temp2 = a[i] % s;
temp2 = temp2 * 10 / s;
b[c[temp2] - 1] = temp1;
c[temp2] = c[temp2] - 1;
}
return b;
}
参考文献:
1、Java数据结构与算法(第二版)
2、http://www.sorting-algorithms.com/
3、http://blog.csdn.net/yexinghai/archive/2009/10/10/4649923.aspx
4、http://yoyo08.iteye.com/blog/464556
5、http://www.java125.cn/article.asp?id=1683
分享到:
相关推荐
常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结常用排序算法总结
java排序算法使用及场景说明 文档后面有一些别人的链接,多在google上搜索Java排序算法,及维基百科上面也有很全的算法介绍。
java实现的常用的几种基本排序算法,插入、交换、选择、归并
JAVA排序算法总结,对常用的算法进行了总结,可以看看哦!!
Java排序算法实现 Java排序算法实现 Java排序算法实现
关于八种常见的排序算法的总结,里面有可运行的Java代码,方便打印
Java排序算法代码.
java排序算法java排序算法插入选择冒泡java排序算法插入选择冒泡
实现合并排序,插入排序,希尔排序,快速排序,冒泡排序,桶排序算法的java实现。
Java常用8大排序算法,包含每种算法详细介绍,及代码如何实现。
Java所有排序算法大全 Java所有排序算法大全 Java所有排序算法大全 Java所有排序算法大全
尚硅谷Java排序算法PPT
Java排序算法 Java排序算法.rar
排序算法总结.doc 排序算法总结.doc 排序算法总结.doc
排序算法,就是如何使得记录按照要求排列的方法。排序算法在很多领域得到相当地重视,尤其是在大量数据的处理方面。一个优秀的算法可以节省大量的资源。在各个领域中考虑到数据的各种限制和规范,要得到一个符合实际...
java最常见的八种排序算法
Java各种排序算法代码.rar
几种内部排序算法总结!(冒泡排序、快速排序、直接插入排序、拆半插入排序、简单选择排序)
java产生多个随机数写入文件中,比较四种排序算法的效率
Java排序算法 Java排序算法 Java排序算法