package Utils.Sort;/***归并排序,要求待排序的数组必须实现Comparable接口*/public class MergeSort implements SortStrategy{ private Comparable[] bridge; /** *利用归并排序算法对数组obj进行排序 */ public void sort(Comparable[] obj) { if (obj == null) { throw new NullPointerException("The param can not be null!"); } bridge = new Comparable[obj.length]; //初始化中间数组 mergeSort(obj, 0, obj.length - 1); //归并排序 bridge = null; } /** *将下标从left到right的数组进行归并排序 *@param obj 要排序的数组的句柄 *@param left 要排序的数组的第一个元素下标 *@param right 要排序的数组的最后一个元素的下标 */ private void mergeSort(Comparable[] obj, int left, int right) { if (left < right) { int center = (left + right)/2; mergeSort(obj, left, center); mergeSort(obj, center + 1, right); merge(obj, left, center, right); } } /** *将两个对象数组进行归并,并使归并后为升序。归并前两个数组分别有序 *@param obj 对象数组的句柄 *@param left 左数组的第一个元素的下标 *@param center 左数组的最后一个元素的下标 *@param right 右数组的最后一个元素的下标 */ private void merge(Comparable[] obj, int left, int center, int right) { int mid = center + 1; int third = left; int tmp = left; while (left <= center && mid <= right) { //从两个数组中取出小的放入中间数组 if (obj[left].compareTo(obj[mid]) <= 0) { bridge[third++] = obj[left++]; } else bridge[third++] = obj[mid++]; } //剩余部分依次置入中间数组 while (mid <= right) { bridge[third++] = obj[mid++]; } while (left <= center) { bridge[third++] = obj[left++]; } //将中间数组的内容拷贝回原数组 copy(obj, tmp, right); } /** *将中间数组bridge中的内容拷贝到原数组中 *@param obj 原数组的句柄 *@param left 要拷贝的第一个元素的下标 *@param right 要拷贝的最后一个元素的下标 */ private void copy(Comparable[] obj, int left, int right) { while (left <= right) { obj[left] = bridge[left]; left++; } }}
看天,看雪,安安静静,不言不语都是好风景。