合并排序

合并排序

算法介绍：

合并排序是建立在归并操作上的一种有效的排序算法。该算法是采用分治法 的一个非常典型的应用。
合并排序法是将两个（或两个以上）有序表合并成一个新的有序表，即把待排序序列分为若干个子序列，每个子序列是有序的。然后再把有序子序列合并为整体有序序列。
将已有序的子序列合并，得到完全有序的序列；即先使每个子序列有序，再使子序列段间有序。若将两个有序表合并成一个有序表，称为2-路归并。合并排序也叫归并排序。

public class MergingRank {

    /**
     * @param args
     */
    public static void main(String[] args) { 
int[] A={10,9,8,7,6,3,6,5,3,4,5,6,2,34,12,52};  //初始数组
MergingRank Merg=new MergingRank();
          Merg. MergeSort(A); 
    }
    public   void MergeSort(int[] A){    //分治法，分成两部分进行排序
        int[] B=new int[A.length/2+1];
        int[] C=new int[A.length/2+1];
        if(A.length>0){
            for(int i=0;i<(A.length/2)-1;i++){
                B[i]=A[i];
            }
            int n=1;
            for(int j=(A.length/2);j<A.length;j++){
                C[n]=A[j];
                n++;
            }
            MergeSort(B);                     //递归调用
            MergeSort(C);
            Merging(B,C,A);

        }

    }
    public     void Merging(int[] B,int[] C,int[] A){  //排序算法
        int i=0,j=0,k=0;
        while((i<B.length)&&(j<C.length)){
            if (B[i]<=C[j]){
                A[k]=B[j];
                i++;
            }
            else{
                A[k]=C[j];
                j++; 
            } 
        };
        if(i==B.length){
            for(int m=j;m<C.length;m++){
                A[k]=C[m];
                k++;
            }
        }
        else {
            for(int n=i;n<B.length;n++){
                A[k]=B[n];
                k++;
            }
        }

    }

}