addresscalculationsort.java

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

import dslib.list.OrderedLinkedListUos;

public class AddressCalculationSort
{
	final int tableSize = 5; // global constant with chosen number of hash values
	
	/**	A method to sort array inVec using address calculation. */
	public void addressCalculationSort(int[ ] inVec)
	{
		/*	Initialize the table. */
		OrderedLinkedListUos[ ] hashLists = new OrderedLinkedListUos[tableSize];
		for (int i = 0; i < tableSize; i++)
			hashLists[i] = new OrderedLinkedListUos();

		/*	Calculate the divisor to be used for hashing. */
		int divisor = (int) Math.ceil((max(inVec) + 1) / tableSize);

		/*	Build the hash lists. */
		for (int i = 0; i < inVec.length; i++)
		{
			int hashValue = hash(inVec[i], divisor);
			hashLists[hashValue].insert(new Integer(inVec[i]));
		}

		/*	Copy over sorted items. */
		int pocket = 0;
		for (int i = 0; i < inVec.length; )
			if (hashLists[pocket].isEmpty())
				pocket++;
			else
			{
					inVec[i] = ((Integer)hashLists[pocket].firstItem()).intValue();
					hashLists[pocket].deleteFirst();
					i++;
			}
	}

	private int hash(int key, int divisor)
	{
		return key / divisor;
	}

	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;		
	}
}