quicksort.java

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

public class QuickSort
{
	/**	Sort array keys using the recursive partition-exchange approach. */
	public void quickSort(int[ ] keys)
	{
		quickSortHelper(keys, 0, keys.length - 1);
	}

	/**	A helper method to perform a partition-exchange sort of the items between
		start and finish. */
	private void quickSortHelper(int[ ] inVec, int start, int finish)
	{
		if (start < finish)
		{
			int split = partition(inVec, start, finish);
			quickSortHelper(inVec, start, split - 1); // sort left subsequence
			quickSortHelper(inVec, split + 1, finish); // sort right subsequence
		}
	}

	/**	Given a sequence of items in array inVec between start and finish, rearrange the
		items so that all items in positions less than split have value <= inVec[split],
		and all items in positions greater than split have value >= inVec[split]. Return split. */
	private int partition(int[ ] inVec, int start, int finish)
	{
		int partitionItem = inVec[start]; // item that will end up in position split
		int i = start;  // lower index
		int j = finish + 1; // upper index
		while (i < j)
		{
			i++;
			/*	Move item i past items <= partitionItem. */
			while ((i < j) && (inVec[i] <= partitionItem))
				i++;
			j--;
			/*	Move item j before items >= partitionItem. */
			while ((i <= j) && (inVec[j] >= partitionItem))
				j--;
			if (i < j) // interchange the large item i with small item j
			{
				int temp = inVec[i];
				inVec[i] = inVec[j];
				inVec[j] = temp;
			}
		}
		/*	Put item j in the first position, and partitionItem in position j. */
		inVec[start] = inVec[j];
		inVec[j] = partitionItem;
		return j;
	}
}