归并排序算法的JAVA实现

王朝java/jsp·作者佚名  2006-02-01
窄屏简体版  字體: |||超大  

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

}

}

}

 
 
 
免责声明:本文为网络用户发布,其观点仅代表作者个人观点,与本站无关,本站仅提供信息存储服务。文中陈述内容未经本站证实,其真实性、完整性、及时性本站不作任何保证或承诺,请读者仅作参考,并请自行核实相关内容。
 
 
© 2005- 王朝網路 版權所有 導航