Java实现归并排序(MergeSort)

/**	归并排序Java实现
 *	MertSort using Java
 * 	by puladiao
 * 	http://blog.verypod.com
 */
class MergeSorter {
	private int nElems;
	private int[] theArray, workSpace;

	public MergeSorter(int[] theArray) {
		nElems = theArray.length;
		this.theArray = theArray;
	}

	public void MergeSort() {
		workSpace = new int[nElems];
		recMergeSort(0, nElems - 1);
	}

	private void recMergeSort(int lowerBound, int upperBound) {
		if (lowerBound == upperBound) {
			return;
		} else {
			int mid = (lowerBound + upperBound) / 2;
			recMergeSort(lowerBound, mid);
			recMergeSort(mid + 1, upperBound);
			merge(lowerBound, mid, upperBound);
		}
	}

	private void merge(int lowerBound, int mid, int upperBound) {
		int leftIndex, rightIndex, index;
		leftIndex = lowerBound;
		index = lowerBound;
		rightIndex = mid + 1;
		while (leftIndex <= mid && rightIndex <= upperBound) {
			if (theArray[leftIndex] < theArray[rightIndex]) {
				workSpace[index++] = theArray[leftIndex++];
			} else {
				workSpace[index++] = theArray[rightIndex++];
			}
		}
		while (leftIndex <= mid) {
			workSpace[index++] = theArray[leftIndex++];
		}
		while (rightIndex <= upperBound) {
			workSpace[index++] = theArray[rightIndex++];
		}
		for (int i = lowerBound; i <= upperBound; i++) {
			theArray[i] = workSpace[i];
		}
	}

	public void display() {
		for (int i = 0; i < nElems; i++) {
			System.out.print(theArray[i] + " ");
		}
		System.out.println("");
	}
}

public class MergeSortApp {
	public static void main(String[] args) {
		int[] arr = new int[] { 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1 };
		MergeSorter ms = new MergeSorter(arr);
		ms.display();
		ms.MergeSort();
		ms.display();
	}
}

发表评论

电子邮件地址不会被公开。 必填项已用*标注