合并排序

闲来无事，来写写合并排序，第一次看到合并排序，我相信大家可能像我一样感觉看的有点迷糊，特别合并排序的思想：是将一个数组分成2个较小有序的数组，然后才进行合并排序。迷糊的地方：主要是下面涂色的地方，在归并前2个数组有序（怎么有序呢？），然后只要大家联想到递归或者树的遍历就知道，在将每个较大的数组拆分的时候呈现一个树形，到最后只有一个数字（有序），然后再依此合并。
import java.util.*;
public class Merge1

{
 
 private int[] bridge;

 public static void main(String args[])
 {
   int[] brige={34,12,43,5,89,3};
 Merge1 mg=new Merge1();
 mg.sort(brige);
 for(int i=0;i<brige.length;i++)
 System.out.println(" "+brige[i]);
 
}
      
 

       /**

       *利用归并排序算法对数组obj进行排序

       */

       public void sort(int[] obj)

       {
 

              bridge = new int[obj.length];                //初始化中间数组

              mergeSort(obj, 0, obj.length - 1);                       //归并排序

             //bridge = null;

       }

 

       /**

       *将下标从left到right的数组进行归并排序

       *@param obj　要排序的数组的句柄

       *@param left 要排序的数组的第一个元素下标

       *@param right 要排序的数组的最后一个元素的下标

       */

       private void mergeSort(int[] 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(int[] 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]<=obj[mid])

                     {

                            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(int[] obj, int left, int right)

       {

              while (left <= right)

              {

                     obj[left] = bridge[left];

                     left++;

              }

       }

}