算法导论——合并排序

合并排序采用了分治法的思路来设计排序算法。
主要步骤：
1：分解数组
2：排序子数组
3：合并排序好的子数组

其代码如下：

public interface Sort<T> {
	
	/**
	 * 返回排序后的数组
	 * @return
	 */
	public T[] sort(T[] array);
	
}


import java.util.Arrays;
import java.util.Comparator;

public abstract class AbstractSort<T> implements Sort<T> {
	
	
	/**
	 * 用于比较数组元素大小
	 */
	protected Comparator<? super T> comp;
	
	public void init(Comparator<? super T> comp){
		this.comp = comp;
	}
	
	public void print(T[] array){
		System.out.println(Arrays.toString(array));
	}
	
	public void swap(T[] array,int i ,int j){
		T temp = array[i];
		array[i] = array[j];
		array[j] = temp;
	}
	
}

import java.util.Arrays;
import java.util.Comparator;

public class MergeSort<T> extends AbstractSort<T> {

	public MergeSort(Comparator<? super T> comp) {
		init(comp);
	}

	@Override
	public T[] sort(T[] array) {
		sort(array, 0, array.length - 1, array.clone());
		return array;
	}

	/**
	 * 对指定区间[start,end]的数组元素进行排序
	 * 
	 * @param start
	 * @param end
	 */
	private void sort(T[] src, int start, int end, T[] clone) {
		if (start < end) {
			int mid = (end + start) / 2;
			sort(src, start, mid, clone);
			sort(src, mid + 1, end, clone);
			merge(src, start, mid + 1, end + 1, clone);
		}
	}

	/**
	 * 合并子数组[start,mid)和子数组[mid,end)。
	 * 
	 * @param src
	 * @param start
	 * @param mid
	 * @param end
	 * @param clone
	 */
	private void merge(T[] src, int start, int mid, int end, T[] clone) {
		System.arraycopy(src, start, clone, start, end - start);
		int leftIndex = start;
		int rightIndex = mid;
		int i = start;
		for (; leftIndex < mid && rightIndex < end; i++) {
			T l = clone[leftIndex];
			T r = clone[rightIndex];
			if (comp.compare(r, l) > 0) {
				src[i] = l;
				leftIndex++;
			} else {
				src[i] = r;
				rightIndex++;
			}
		}
		if (leftIndex < mid) {
			System.arraycopy(clone, leftIndex, src, i, mid - leftIndex);
		} else // if(rightIndex == end)
		{
			// 复制右半部分
			System.arraycopy(clone, rightIndex, src, i, end - rightIndex);
		}
	}

	public static void main(String[] args) {
		MergeSort<Integer> s = new MergeSort<Integer>(new Comparator<Integer>() {

			@Override
			public int compare(Integer o1, Integer o2) {
				return o1 - o2;
			}
		});
		Integer[] array = new Integer[] { 3, 5, 9, 8 };
		s.sort(array);
		System.out.println(Arrays.toString(array));
	}

	@Override
	public String toString() {
		return "合并排序";
	}

}