sort.java

来自「The running time of quicksort can be imp」· Java 代码 · 共 100 行

public class Sort
{
	private double[] sourceArray;
	private double[] targetArray;
	private double key;
	private static int flag;
	private static int vituralFlag;

	public Sort(double[] sourceArray)
	{
		this.sourceArray = sourceArray;
		targetArray = new double[sourceArray.length];
		flag = 0;
		vituralFlag = 0;
	}

	/* The method to output the result of both insertion sort and quick sort. */
	public void result()
	{
		for (int n = 0; n < targetArray.length; n ++)
			System.out.println(targetArray[n]);
	}

	/* The origin edition of insertion sort. */
	public void insertionSort(int leftBound, int rightBound)
	{
		double key = 0;
		int i = leftBound;
		for (int j = leftBound + 1; j <= rightBound; j++ )
		{
			key = sourceArray[j];
			i = j ;
			while (i > leftBound && sourceArray[i - 1] > key)
			{
				sourceArray[i] = sourceArray[i - 1];
				i --;
			}
			sourceArray[i] = key;
		}

		/* Although you may fell strange that the following steps are useless: 
			 it transfers the result to a new array, 
			 it is based on the consideration of the efficiency of the later quick insertion sort. 
			 The result of quick sort must be stored in a different array form the source one, 
			 but the result of insertion sort is just stored in the source array. 
			 However, in the quick insertion sort, 
			 the result have to be stored in an array different from the source one no matter which kind of sort is using, 
			 or the process of sort will be in a mess. 
			 We take it into consideration so that the "turning point" can be as accurate as possible, 
			 and the quick insertion sort can be as efficient as possible. */
		for (int n = leftBound; n <= rightBound; n ++)
		{
			targetArray[vituralFlag] = sourceArray[n];
			vituralFlag ++;
		}
	}

	/* The origin edition of quick sort. */
	public void quickSort(int leftBound, int rightBound)
	{
		if (leftBound < rightBound)
		{
			int newBound = partition(leftBound, rightBound);
			quickSort(leftBound, newBound - 1);
			combine(newBound);
			quickSort(newBound + 1, rightBound);
		}
		else if (leftBound == rightBound)
			combine(leftBound);
	}

	/* The method to divide the array into shorter ones. */
	private int partition(int leftBound, int rightBound)
	{
		int i = leftBound - 1;

		for (int j = leftBound; j <= rightBound - 1; j ++)
			if (sourceArray[j] <= sourceArray[rightBound])
			{
				i ++;
				exchange(i,j);
			}
		exchange(i + 1, rightBound);
		return i + 1;
	}

	private void exchange(int i, int j)
	{
		double temp = sourceArray[i];
		sourceArray[i] = sourceArray[j];
		sourceArray[j] = temp;
	}

	/* The method to combine the result of quick sort into a new array. */
	private void combine(int i)
	{
		targetArray[flag] = sourceArray[i];
		flag ++;
	}
}