mergesort.java

来自「这是Java的模式编程」· Java 代码 · 共 43 行

package Strategy;

import java.lang.Comparable;

public class Mergesort extends SortStrategy
{
	private static void mergeSort(Comparable [] a,Comparable [] tmpArray,int left,int right)
	{
		if(left < right)
		{
			int center = (left + right)/2;
			mergeSort(a,tmpArray,left,center);
			mergeSort(a,tmpArray,center+1,right);
			merge(a,tmpArray,left,center+1,right);
		}
	}
	public static void merge(Comparable [] a,Comparable [] tmpArray,int leftPos,int rightPos,int rightEnd )
	{
		int leftEnd = rightPos - 1;
		int tmpPos = leftPos;
		int numElements = rightPos - leftPos + 1;
		while(leftPos <= leftEnd && rightPos <= rightEnd)
			if(a[leftPos].compareTo(a[rightPos]) <= 0)
				tmpArray[tmpPos++] = a[leftPos ++];
			else
			    tmpArray[tmpPos++] = a[rightPos ++];
	    while(leftPos <= leftEnd)
	    	tmpArray[tmpPos ++] = a[leftPos ++];
	    while(rightPos <= rightEnd)
	    	tmpArray[tmpPos ++] = a[rightPos ++];
	    for(int i=0;i < numElements;i++,rightEnd --)
	    	a[rightEnd] = tmpArray[rightEnd];
			    
	}
	public void sort(Comparable [] a)
	{
		Comparable [] tmpArray = new Comparable[a.length];
		mergeSort(a,tmpArray,0,a.length-1);
	    printInfor("Mergesort");
	    printArray(a);
		
	}
}