threemethodstimed.java

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

public class ThreeMethodsTimed
{
	/**	Return the largest value in the array. */
	public static short getMax(short[] array)
	{
		short largest = array[0];
		for (int i = 1; i < array.length; i++)
			if (array[i] > largest)
			largest = array[i];
		return largest;
	}

	/**	Performs a selection sort on the array. */
	public static void selectSort(short[] array)
	{
		int smallIndex, i, j;
		short temp;
		for (i = 0; i < array.length-1; i++)
		{
			smallIndex = i;
			for (j = i+1; j < array.length; j++)
				if (array[j] < array[smallIndex]) 
					smallIndex = j;
			if (smallIndex != i)
			{
				temp = array[i];
				array[i]= array[smallIndex];
				array[smallIndex] = temp;
			}
		}
	}

	/**	Find all permutations of the last p elements in the array. */
	public static void permute(char[] array, int p)
	{
		int i, s;
		char temp;
		if (p != 1)
		{
			s = array.length - p;
			//for each possible character in position s, permute the remaining characters
			permute(array, p - 1);
			for (i = s + 1; i < array.length; i++)
			{
				temp =  array[s];
				array[s] = array[i];
				array[i] = temp;
				permute(array, p - 1);
			}
			// left shift each character back to its original position
			temp = array[s];
			for (i = s; i < array.length - 2; i ++)
				array[i] = array[i + 1];
			array[array.length - 1] = temp;
		}
	}
	
	/**	Returns a string to display all the characters, looks like one big string. */
	public static String display(char[] arr)
	{
		String temp = new String();
		for (int i = 0; i < arr.length; i++)
			temp += arr[i];
		return temp;
	}
}