JAVA实现归并排序算法 - 编程入门网

JAVA实现归并排序算法

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++; 　　　　　　　} } }

凌众科技专业提供服务器租用、服务器托管、企业邮局、虚拟主机等服务，公司网站：http://www.lingzhong.cn 为了给广大客户了解更多的技术信息，本技术文章收集来源于网络,凌众科技尊重文章作者的版权，如果有涉及你的版权有必要删除你的文章，请和我们联系。以上信息与文章正文是不可分割的一部分,如果您要转载本文章,请保留以上信息，谢谢!