归并排序（Merge sort）算法 [# 27]

Merge sort 算法的思想就是把数组分成更小的数组，合并的时候再排序。由于是二分，所以总的时间为 T(n) = 2 T(n/2) + \theta (n) = O(n * lgn)。

public void mergeSort(int[] array, int start, int end) {
	if (start < end) {
		int mid = start + (end - start) / 2;
		mergeSort(array, start, mid);
		mergeSort(array, mid + 1, end);
		merge(array, start, mid, end);
	}
}

public void merge(int[] array, int start, int mid, int end) {
	int[] temp1 = new int[mid - start + 2];
	int[] temp2 = new int[end - mid + 1];
	
	for (int i = start; i <= mid; i++) {
		temp1[i - start] = array[i];
	}
	temp1[mid - start + 1] = Integer.MAX_VALUE;
	
	for (int i = mid + 1; i <= end; i++) {
		temp2[i - mid - 1] = array[i];
	}
	temp2[end - mid] = Integer.MAX_VALUE;
	
	int p1 = 0;  //pointer of temp1 array
	int p2 = 0;  //pointer of temp2 array
	
	//alert, not index = 0
	int index = start;
	//the while loop will stop if at least one of the array is empty 
	while ((p1 < mid - start + 1) && (p2 < end - mid)) {
		if (temp1[p1] <= temp2[p2]) {
			array[index++] = temp1[p1++];
		} else {
			array[index++] = temp2[p2++];
		}
	}
	//check whether temp1 is empty
	if (p1 == mid - start + 1) {
		//alert, not p2 != end - mid - 1
		while (p2 != end - mid) {
			array[index++] = temp2[p2++];
		}
	} 
	//check whether temp2 is empty
	if (p2 == end - mid) {
		//alert, not p1 != mid - start;
		while (p1 != mid - start + 1) {
			array[index++] = temp1[p1++];
		}
	} 
}

注意，有很多人写的 mergesort 都不能处理当数组中有多个 Integer.MAX_VALUE的情况。但是，本文的算法是可以的。

转载请注明出处：http://blog.csdn.net/beiyeqingteng