java 实现 归并排序算法 MergeSort，

public class MergeSort {
	
	private static void mergeSort(Comparable[] data,Comparable[] tmpArray, int left, int right){
		if(left < right){
			int center = (left + right) / 2;
			mergeSort(data, tmpArray, left, center);
			mergeSort(data, tmpArray, center + 1, right);
			merge(data, tmpArray, left,center + 1, right);
		}
	}
	
	
	private static void merge(Comparable[] data, Comparable[] tmpArray, int leftPos, int rightPos, int rightEnd){
		int leftEnd = rightPos - 1;
		int tmpPos = leftPos;
		int numElements = rightEnd - leftPos + 1;
		
		while(leftPos <= leftEnd && rightPos <= rightEnd)
			if(data[leftPos].compareTo(data[rightPos]) <= 0)
				tmpArray[tmpPos++] = data[leftPos++];
			else
				tmpArray[tmpPos++] = data[rightPos++];
		while(leftPos <= leftEnd)
			tmpArray[tmpPos++] = data[leftPos++];
		while(rightPos <= rightEnd)
			tmpArray[tmpPos++] = data[rightPos++];
		
		for(int i = 0; i < numElements; i++, rightEnd--)
			data[rightEnd] = tmpArray[rightEnd];
			
	}
	
	public static void mergeSort(Comparable[] data){
		Comparable[] tmpArray = new Comparable[data.length];
		mergeSort(data,tmpArray,0,data.length - 1);
	}
	
	
	public static void main(String[] args){
		Comparable[] a = new Comparable[30];
		for(int i = 0; i < a.length; i++)
			a[i] = (int) (Math.random() * 100);
		for(int i = 0; i < a.length; i++)
			System.out.print(a[i] + " , ");
		System.out.println("");
		mergeSort(a);
		for(int i = 0; i < a.length; i ++)
			System.out.print(a[i] + " , ");
	}

}

评论

1 楼 fouri 2009-10-10  

有注释就更好了