归并排序算法的JAVA实现

来源：http://blog.csdn.net/Linyco 作者：Linyco 出处：巧巧读书 2006-03-12 进入讨论组

• 关 键 词：
• java

精华网络内容 :http://www.qqread.com/network/

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

              } }

}

更多内容请看Java环境安装配置、Java编程开发手册、JAVA算法专题，或进入讨论组讨论。

【收藏此文】【大 中 小】【打印】【关闭】

较早的文章：Java操作Excel电子表格

较新的文章：Java的网络程序设计(1)