sorts.java

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

public class Sorts
{
	/**	Merge start1st through start2nd - 1 with start2nd through end2nd
		in array using temp as a temporary array.
		Analysis : Time = O(end2nd - start1st) */
	public static void merge(short[] array, short[] temp, int start1st, int start2nd, int end2nd)
	{   
		/*	cur1 and cur2 are the indices of the current items of each sequence.
			cur3 is the index of the next location of temp. */

		/*	Repeatedly copy the smaller item into temp. */
		int cur1 = start1st, cur2 = start2nd, cur3 = start1st;
		while ((cur1 < start2nd) && (cur2 <= end2nd))
		{
			if (array[cur1] <= array[cur2])
			{
				temp[cur3] = array[cur1];
				cur1++;
				cur3++;
			}
			else
			{
				temp[cur3] = array[cur2];
				cur2++;
				cur3++;
			}
		}

		/*	Copy remainder of the first sequence (if any) into temp. */
		while (cur1 < start2nd)
		{
			temp[cur3] = array[cur1];
			cur1++;
			cur3++;
		}
		
		/*	Copy remainder of the second sequence (if any) into temp. */
		while (cur2 <= end2nd)
		{
			temp[cur3] = array[cur2];
			cur2++;
			cur3++;
		}

		/*	Copy items from temp back into array. */
		cur1 = start1st;
		cur3 = start1st;
		while (cur3 <= end2nd)
		{
			array[cur1] = temp[cur3];
			cur1++;
			cur3++;
		}
	}


	/** Sort array using the merge sort algorithm.
		The method uses the simple merge algorithm to sort an array.
		Analysis : Time = O(n log n), where n is the length of array */
	public static void mergeSort(short[] array)
	{
		/* 	seqSize is the current size of the sequence being merged.
			start1st, start2nd, end2nd are the ends of the consecutive sequences being merged. */
		short[] temp = new short[array.length];

		int seqSize = 1;
		while(seqSize < array.length)
		{
			int start1st = 0;
			int start2nd = seqSize;
			while(start2nd < array.length)
			{
				int end2nd = Math.min((start2nd + seqSize - 1), (array.length-1));
				merge(array, temp, start1st, start2nd, end2nd);
				start1st = end2nd + 1;
				start2nd = start1st + seqSize;
			}
			seqSize *= 2;
		}
	}
	
	
	/** The method uses the simple merge, with selectSort to create sequences of 16. */
	public static void mergeSelectSort(short[] array)
	{
		int seqSize = 16, start1st, start2nd, end2nd, i = 0;
		short[] temp = new short[array.length];
		
		while(i + 15 < array.length)
		{
			selectSort(array, i, i + 15);
			i += 16;
		}
		
		/*	last section smaller than 16 */
		if(i != array.length)  
			selectSort(array, i, array.length-1);

		while(seqSize < array.length)
		{
			start1st = 0;
			start2nd = seqSize;
			while (start2nd < array.length)
			{
				end2nd = Math.min((start2nd + seqSize - 1), (array.length - 1));
				merge(array, temp, start1st, start2nd, end2nd);
				start1st = end2nd + 1;
				start2nd = start1st + seqSize;
			}
			seqSize *= 2;
		}
	}
	
	
	/**	Performs a selection sort on a segment of the array. */
	public static void selectSort(short[] array, int front, int back)
	{
		int smallIndex, i, j;
		short temp;
		for(i = front; i <= back; i++)
		{
			smallIndex = i;
			for(j = i+1; j <= back; j++)
				if(array[j] < array[smallIndex]) 
					smallIndex = j;
			if(smallIndex != i)
			{
				temp = array[i];
				array[i]= array[smallIndex];
				array[smallIndex] = temp;
			}
		}
	}


	/** Returns a string displaying the contents of the array. */
	public static String display(short[] arr)
	{
		String temp = new String();
		for(int i = 0; i < arr.length; i++)
			temp += arr[i] + ", ";
		return temp;
	}
}