radixsort.java

来自「自己写的search engine, 有 boolean search, fuz」· Java 代码 · 共 67 行

package searchingEngine.utilites.sorting;

public class RadixSort {

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub

	}

	public int[] Radix(int source[], int elements)
	{
		int temp[] = new int[elements];

		// N int-Zahlen nach byte 0 von source nach temp sortieren
		// das lsb ... least-significant-byte
		counting_sort_by_radix(0, elements, source, temp);

		// N int-Zahlen nach byte 1 von temp nach source sortieren
		counting_sort_by_radix(1, elements, temp, source);

		// N int-Zahlen nach byte 2 von source nach temp sortieren
		counting_sort_by_radix(2, elements, source, temp);

		counting_sort_by_radix(3, elements, temp, source);

		return source;
	}
	private int GETBYTE(int val, int bytenum)
	{
		return (val >> (8 * bytenum)) & 0xff;
	}
	private void counting_sort_by_radix(int int_byte, int elements, int source[], int dest[])
	{
		final int k = 256;
		int count[] = new int[k];
		int i;
		int source_i;

		for (i=0; i<elements; i++)
		{
			source_i = GETBYTE(source[i], int_byte);
			count[source_i]++;
		}

		// sp鋞ere Array-Indices berechnen:
		// k0[0]		-> dest[0]
		// ...
		// k0[count[k0]]	-> dest[count[k0]]
		// k1[0]		-> dest[count[k0]+1]
		// ...
		// k1[count[k1]]	-> dest[count[k0]+count[k1]]
		// ...
		for (i=1; i<k; i++)
			count[i] += count[i-1];
		for (i=elements-1; i>=0; i--)
		{
			source_i = GETBYTE(source[i], int_byte);
			dest[count[source_i]-1] = source[i];
			count[source_i]--;
		}
	}

}