radixsort.java

国外的数据结构与算法分析用书

import dslib.dispenser.LinkedQueueUos;

public class RadixSort
{
	/**	The kth digit (from the right) of number. */ 
	public int digitSelect(int k, int number)
	{
		String temp = k + "";
		if (temp.length() < number)
			return 0;
		temp = temp.charAt(temp.length() - number) + "";
		return Integer.parseInt(temp);
	}

	/**	Return the maximum value in the array. */
	public int max(int[] inVec)
	{
		int largest = inVec[0];
		for (int i = 1; i < inVec.length; i++)
			if (inVec[i] > largest)
				largest = inVec[i];
		return largest;
	}

	/**	Procedure to perform a radix sort using FIFO queues. */
	public void radixSort(int[ ] inVec)
	{
		LinkedQueueUos[ ] pockets = new LinkedQueueUos[10];
		for (int i = 0; i < pockets.length; i++)
			pockets[i] = new LinkedQueueUos();
		int digitsInKey = (int)Math.floor(Math.log(max(inVec))/Math.log(10)) + 1;
		for (int pass = 1; pass <= digitsInKey; pass++)
		{
			for (int i = 0; i < inVec.length; i++)
			{
				int curKey = inVec[i];
				int digit = digitSelect(curKey, pass);
				pockets[digit].insert(new Integer(curKey));
			}
			int j = 0;
			for (int i = 0; i < pockets.length; i++)
				while (!pockets[i].isEmpty())
				{
					inVec[j] = ((Integer) pockets[i].item()).intValue();
					pockets[i].deleteItem();
					j++;
				}
		}
	}
}