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

2012/4/1----基数排序

程序员文章站 2022-05-24 15:06:49
...

基数排序的核心思想是:把待排序的数组N中的数据分解成为个位,十位,百位.....然后再从个位开始排序,得到第一个数组N1,然后再把N1数组的十位进行排序得到N3,再对N3数组的百位进行排序得到N4,依次这样排序,直到数组中的所有数据的位数都用来排过序了,就可以得到我们所需要的排序数组了。

以下就是过程代码:

/*
 * 基数排序的java实现
 * @version 1.0 2012/4/1
 * @author akon
 */
package com.akon405.www;

public class RadixSort {
	public RadixSort(int[] A,int a){
		int[][] temp=new int[10][A.length];
		int[] B=new int[10];
		
		int i,j,k,m;
		int n=1;
		
		for(i=1;i<=a;i++){
			int p=0;
			//想temp中存数据,数据来自A
			for(j=0;j<A.length;j++){
				k=A[j]/n%10;//A[j]基数位的数值:0--9
				temp[k][B[k]]=A[j];//存放在二维数组  中
				B[k]++;//起始值为初始化的0,由B[k]的数值可以得到在temp中的第k行存在多少个数值			
			}
			//从temp中取数据到A
			for(j=0;j<10;j++){
				if(B[j]!=0){//如果二位数组temp所在的列存放的有数据,才对这列进行取数据操作
					for(m=0;m<B[j];m++){
						A[p]=temp[j][m];//按每次排序之后的顺序存放在A数组中
						p++;
					}
				}
				B[j]=0;//供下一次使用,
			}
			n=n*10;
		}

	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		int[] A={21,19,1,8,76};
		int a=2;//数据的最大位数,这里最大为两位数,所以a为2
		System.out.print("排序结果:");
		new RadixSort(A,a);
		for(int i=0;i<A.length;i++){
			System.out.print(A[i]+",");
		}
	}

}