Java之基数排序

该基数排序算法先对低位进行排序，然后对高位排序，而对每一位排序时又采用了计数排序算法。代码如下：

 

package cn.lifx.array.sort;

public class RadixSort 
{
	public static void main(String[] args)
	{
		int[] a = {123, 963, 234, 546, 361, 798, 479, 310, 617, 892};
		
		Display(a, "Before sort:");
		
		a = radixSort(a);
		
		Display(a, "After sort:");
	}
	
	public static int[] radixSort(int[] a)
	{
		int[] b = new int[a.length];
		
		for(int i=0; i<a.length; i++)
			b[i] = a[i];
			
		for(int i=1; i<=a.length; i++)
			b = countSort(b, i);
		
		return b;
	}
	
	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;
	}
	
	public static void Display(int[] a, String str)
	{
		System.out.println(str);
		for(int i=0; i<a.length; i++)
			System.out.print(a[i] + "  ");
		System.out.println();
	}
}

 

结果如下：

 

Before sort:
123  963  234  546  361  798  479  310  617  892  
After sort:
123  234  310  361  479  546  617  798  892  963  

 

 

评论

1 楼 haisheng 2010-01-24  

for(int i=1; i<=a.length; i++)  
            b = countSort(b, i); 

假如a有个元素的位数大于数组长度，就会出问题。