欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

Java语言实现基数排序代码分享

程序员文章站 2024-02-18 20:52:10
算法思想:依次按个位、十位...来排序,每一个pos都有分配过程和收集过程,array[i][0]记录第i行数据的个数。 package sorting; /*...

算法思想:依次按个位、十位...来排序,每一个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相关专题,如有不足之处,欢迎留言指出。感谢朋友们对本站的支持!

上一篇: 五种 JSP页面跳转方法详解

下一篇: