归并排序

归并排序，时间复杂度O(nlgn),相比快速排序和堆排序，优势是排序稳定。通过两两分拆、归并实现。在子数组长度小于等于7(一说50)时可采用插入排序来提高效率(但我在本机上测试，两者带来的提升并不明显)。JDK自带的Collections.sort方法采用的即是归并排序。

public class MergeSort {

	private int[] temp;

	public void sort(int arr[], int start, int to) {
		if (arr == null || arr.length == 0 || start < 0 || end < 0) {
			return;
		}
		if (start >= to) {
			return;
		}
		int middle = (start + to) >> 1;
		sort(arr, start, middle);
		sort(arr, middle + 1, to);
		merge(arr, start, middle, to);
	}

	public void merge(int[] arr, int start, int middle, int end) {
		int index = start;
		int from = start;
		int to = middle + 1;
		while (from <= middle && to <= end) {
			if(arr[from]<=arr[to]){
				temp[index++]=arr[from++];
			}else{
				temp[index++]=arr[to++];
			}
		}
		while(from<=middle){
			temp[index++]=arr[from++];
		}
		while(to<=end){
			temp[index++]=arr[to++];
		}
		while(start<=end){
			arr[start]=temp[start++];
		}
	}
}

评论

1 楼 hyj1254 2011-09-08  

诸位“踩”可以，但请赐教下原因，谢谢。