归并排序（merge sort）——数据结构与算法复习

因为校园招聘马上要开始 了，所以马上来温习一下 数据结构与算法的内容，今天为大家带来我刚写的还带有余温的归并排序——merge sort。

废话不说，代码端上（用java实现的泛型数组排序）：

package kevin.sort;

import java.util.Arrays;

public class SortInPaper {

	/**
	 * 用归并排序的方法对一个数组进行排序，输出有序数组
	 * @param <T> 数组元素的类型，这个类型应该实现Comparable接口，因为merge sort是基于比较的
	 * 			     排序算法。当然我们也可以在方法的参数列表中添加一个Comparator类型的参数，由用
	 * 			     户自定义排序（比较）的依据或方式 
	 * @param a   被排序的数组
	 * @param beg 被排序的范围的开始
	 * @param end 被排序的范围的结束
	 */
	public static <T extends Comparable<? super T>> void mergeSort(T[] a,
			int beg, int end) {
		if (beg < end) {
			int mid = (beg + end) / 2; //划分点
			mergeSort(a, beg, mid);   //对左半部分进行排序
			mergeSort(a, mid + 1, end); //对右半部分进行排序
			merge(a, beg, mid, end);  //合并子问题的结果
		}
	}

	/**
	 * 对一个数组 的两个有序部分进行排序
	 * @param <T> 数组元素的类型
	 * @param a 要进行排序的数组
	 * @param beg 左半部分第一个元素的索引
	 * @param mid 左半部分最后一个元素的索引，同时也是右半部分第一个元素左边相邻的元素
	 * @param end 右半部分最后一个元素的索引 
	 */
	private static <T extends Comparable<? super T>> void merge(T[] a, int beg,
			int mid, int end) {
		T[] left = Arrays.copyOfRange(a, beg, mid + 1); //左半部分的数组元素的copy
		T[] right = Arrays.copyOfRange(a, mid + 1, end + 1); //右半部分的数组元素的copy

		int i = 0;
		int j = 0;
		int k = beg;  //用来跟踪a中的元素
		//先把较小的元素copy到a中，依次递推
		while (i < left.length && j < right.length) {
			if (left[i].compareTo(right[j]) > 0) { 
				a[k++] = right[j++];
			} else {
				a[k++] = left[i++];
			}
		}

		//可能左右两个数组中还有元素没有被复制到a中，所以把剩下的元素复制过去 
		if (i < left.length) {
			while (i < left.length) {
				a[k++] = left[i++];
			}
		} else if (j < right.length) {
			while (j < right.length) {
				a[k++] = right[j++];
			}
		}
	}
}

还请大家指教，看有什么地方 还需要修改的。。thx~~~~~