归并算法详解

MergeSort，归并排序。

[1] 归并排序的原理

1.1 将两个有序数组合并成一个有序数组

两个数组，每一个数组内部都是有序的，比如：
a{5,7} 和 b{6,11,37}

我们申请足够大的空间，来放排好序的数组。比如这个数组叫 c{}。

每次取两个数组中最小的数，进行比较，小的取出放入 c{}。
如此将两个数组中的元素都取完，全部放入 c{}，c{} 中就是一个有序的数组。比如：

第1次：5和6比较，5较小，所以 a{7}, b{6,11,37} -> c{5}
第2次：7和6比较，6较小，所以 a{7}, b{11,37} -> c{5,6}
第3次：7和11比较，7较小，所以 a{}, b{11,37} -> c{5,6,7}
第4次：a{} 空了，所以 b{} 中剩下的都是排好序的大的，所以 a{}, b{} -> c{5,6,7,11,37}

1.2 递归产生有序数组

每次：把一个无序数组，分成前后两半（根据数组中的元素个数，就可以确定到哪里是一半），首先对前一半进行递归调用，然后对后一半进行递归调用。最后归并，产生一个完整的有序数组。

比如：{7, 5, 37, 6, 11}，

一共有5个元素，5/2=2，所以分成 {7,5} {37,6,11}。

   对{7,5} 进行递归调用，一共有2个元素，2/2=1，所以分成 {7} {5}。
   对{7} 进行递归调用，发现到头了，返回。
   对{5} 进行递归调用，发现到头了，返回。
   于是归并 {7} {5}，得到有序数组 {5,7}，返回。

   对{37,6,11} 进行递归调用，一共有3个元素 3/2=1，所以分成 {37} {6,11}。
   对{37} 进行递归调用，发现到头了，返回。

   对{6,11} 进行递归调用，一共有2个元素 2/2=1，所以分成 {6} {11}。
     对{6} 进行递归调用，发现到头了，返回。
     对{11} 进行递归调用，发现到头勒，返回。
     于是归并 {6} {11}，得到有序数组 {6,11}，返回。

   于是归并 {37} {6,11}，得到有序数组 {6,11,37}，返回。

于是归并 {5,7} {6,11,37}，得到有序数组 {5,6,7,11,37}，返回。排序完成。

[2] 归并排序的实现

package testAlgorithm;

import java.util.Arrays;

/**
 * @author derek zhan
 * @version 
 */
@SuppressWarnings("unchecked")
public class MergeSortTest
{
    //排序中的临时数组
    private Comparable [] tmpArray ;
    
    public static void main(String[] args)
    {
        Integer [] obj = {1,4,7,2,5,8};
        MergeSortTest mst = new MergeSortTest();
        mst.sort(obj);
        System.out.println(Arrays.toString(obj));
        Integer[] obj2 = {8,5,2,7,4,1};
        mst.mergeSort2(obj2);
        System.out.println(Arrays.toString(obj2));
    }
    
    /** 
    * *利用归并排序算法对数组obj进行排序 
    */ 
    public void sort(Comparable[] obj) { 
        tmpArray = new Comparable[obj.length];// 初始化中间数组 
        mergeSort1(obj, 0, obj.length - 1); // 归并排序 
        tmpArray = null; 
    } 
    
    //第一个种方法
    /**
     * 递归划分成2个数组
     * @param obj 要排序的数组
     * @param left 数组中第一个元素下标
     * @param right 数组最后一个元素的下标
     */
    public void mergeSort1(Comparable[] obj,int left,int right){
        if(left < right){//只要不是数组的最后一个元素
            int center = (left+right)/2;
            mergeSort1(obj, left, center); //划分成左数组
            mergeSort1(obj, center+1, right);//划分成右数组
            merge1(obj, left, center, right);//合并2一个数组并排序
        }
    }
    //第二种方法
    public void mergeSort2(Comparable[] obj){
        int n = obj.length;
        if(n<=1) return; //如果只有一个元素则返回.
        Comparable left[] = new Comparable[n/2]; //左数组
        Comparable right[] = new Comparable[n-n/2];  //右数组
        for(int i=0,leftPos=left.length; leftPos<obj.length; i++,leftPos++){
            if(i<left.length){ //给左数组赋值
                left[i] = obj[i];
            }
            //给右数组赋值
            right[i] = obj[leftPos];
            
        }
        mergeSort2(left);
        mergeSort2(right);
        merge2(obj, left, right);
    }
    
    /**
     * 合并数组并排序
     * @param obj 要合并的数组
     * @param left 左边数组第一个元素下标
     * @param center 左边数组最后一个元素下标
     * @param right 右边数组最后一个元素下标
     */
    public void merge1(Comparable[] obj,int left,int center,int right){
        int midd = center+1;
        int temp = left;
        int third = left;
        while(left <= center && midd <= right){
            if(obj[left].compareTo(obj[midd])<=0){ //比较2个数组中的值，把小值放入临时数组
                tmpArray[third++] = obj[left++]; 
            }else{
                tmpArray[third++] = obj[midd++]; 
            }
        }
        //如果第一个数组已经全部比较完了，那么我们只要直接复制第二个数组的条目到合并数组中即可 
        while(midd<=right){
            tmpArray[third++] = obj[midd++]; 
        }
        //如果第二个数组已经全部比较完了，那么我们只要直接复制第一个数组的条目到合并数组中即可 
        while(left <= center){
            tmpArray[third++] = obj[left++]; 
        }
        //拷贝bridge to obj数组
        while(temp<=right){
            obj[temp] = tmpArray[temp];
            temp++;
        }
    }
    
    //第二种合并方法
    public void merge2(Comparable[] obj,Comparable[] left,Comparable[] right){
        int leftLength = left.length-1;
        int rightLength = right.length-1;
        int k=0; 
        int leftPos=0,rightPos=0; // left数组下标, right数组下标 
        while(leftPos<=leftLength||rightPos<=rightLength){ 
            Comparable temp = null; 
            if(leftPos>leftLength){  //如果第一个数组已经全部比较完了，那么我们只要直接复制第二个数组的条目到合并数组中即可 
                temp=right[rightPos++]; 
            }else if(rightPos>rightLength){  //如果第二个数组已经全部比较完了，那么我们只要直接复制第一个数组的条目到合并数组中即可 
                temp=left[leftPos++]; 
            }else if(left[leftPos].compareTo(right[rightPos])>0){  //把比较的两个条目中关键值小的放到合并数组中 
                temp=right[rightPos++]; 
            }else{ 
                temp=left[leftPos++]; 
            } 
            obj[k++]=temp; //把比较完的值放入数组
            } 
        } 
}

  

最后执行结果：

[1, 2, 4, 5, 7, 8]
[1, 2, 4, 5, 7, 8]