归并排序(Merge Sort)

发布时间:2018-04-20作者:laosun阅读(530)

归并排序(Merge

java归并排序(Merge Sort),归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

    基本思想:

    归并(Merge)排序法是将两个(或两个以上)有序表合并成一个新的有序表,即把待排序序列分为若干个子序列,每个子序列是有序的。然后再把有序子序列合并为整体有序序列。

    归并排序示例:

    1524195580703059084.jpg

    合并方法:

    设r[i…n]由两个有序子表r[i…m]和r[m+1…n]组成,两个子表长度分别为n-i +1、n-m。

    1. j=m+1;k=i;i=i; //置两个子表的起始下标及辅助数组的起始下标

    2. 若i>m 或j>n,转⑷ //其中一个子表已合并完,比较选取结束

    3. //选取r[i]和r[j]较小的存入辅助数组rf
      如果r[i]<r[j],rf[k]=r[i]; i++; k++; 转⑵
      否则,rf[k]=r[j]; j++; k++; 转⑵

    4. //将尚未处理完的子表中元素存入rf
      如果i<=m,将r[i…m]存入rf[k…n] //前一子表非空
      如果j<=n ,  将r[j…n] 存入rf[k…n] //后一子表非空

    5. 合并结束。

    public class MergeSortTest {    
        
        public static void main(String[] args) {    
            int[] data = new int[] { 5, 3, 6, 2, 1, 9, 4, 8, 7 };    
            print(data);    
            mergeSort(data);    
            System.out.println("排序后的数组:");    
            print(data);    
        }    
        
        public static void mergeSort(int[] data) {    
            sort(data, 0, data.length - 1);    
        }    
        
        public static void sort(int[] data, int left, int right) {    
            if (left >= right)    
                return;    
            // 找出中间索引    
            int center = (left + right) / 2;    
            // 对左边数组进行递归    
            sort(data, left, center);    
            // 对右边数组进行递归    
            sort(data, center + 1, right);    
            // 合并    
            merge(data, left, center, right);    
            print(data);    
        }    
        
        /**  
         * 将两个数组进行归并,归并前面2个数组已有序,归并后依然有序  
         *   
         * @param data  
         *            数组对象  
         * @param left  
         *            左数组的第一个元素的索引  
         * @param center  
         *            左数组的最后一个元素的索引,center+1是右数组第一个元素的索引  
         * @param right  
         *            右数组最后一个元素的索引  
         */    
        public static void merge(int[] data, int left, int center, int right) {    
            // 临时数组    
            int[] tmpArr = new int[data.length];    
            // 右数组第一个元素索引    
            int mid = center + 1;    
            // third 记录临时数组的索引    
            int third = left;    
            // 缓存左数组第一个元素的索引    
            int tmp = left;    
            while (left <= center && mid <= right) {    
                // 从两个数组中取出最小的放入临时数组    
                if (data[left] <= data[mid]) {    
                    tmpArr[third++] = data[left++];    
                } else {    
                    tmpArr[third++] = data[mid++];    
                }    
            }    
            // 剩余部分依次放入临时数组(实际上两个while只会执行其中一个)    
            while (mid <= right) {    
                tmpArr[third++] = data[mid++];    
            }    
            while (left <= center) {    
                tmpArr[third++] = data[left++];    
            }    
            // 将临时数组中的内容拷贝回原数组中    
            // (原left-right范围的内容被复制回原数组)    
            while (tmp <= right) {    
                data[tmp] = tmpArr[tmp++];    
            }    
        }    
        
        public static void print(int[] data) {    
            for (int i = 0; i < data.length; i++) {    
                System.out.print(data[i] + "\t");    
            }    
            System.out.println();    
        }    
        
    }

    归并的迭代算法

    1 个元素的表总是有序的。所以对n 个元素的待排序列,每个元素可看成1 个有序子表。对子表两两合并生成n/2个子表,所得子表除最后一个子表长度可能为1 外,其余子表长度均为2。再进行两两合并,直到生成n 个元素按关键码有序的表。

    void print(int a[], int n){  
        for(int j= 0; j<n; j++){  
            cout<<a[j] <<"  ";  
        }  
        cout<<endl;  
    }  
      
    //将r[i…m]和r[m +1 …n]归并到辅助数组rf[i…n]  
    void Merge(ElemType *r,ElemType *rf, int i, int m, int n)  
    {  
        int j,k;  
        for(j=m+1,k=i; i<=m && j <=n ; ++k){  
            if(r[j] < r[i]) rf[k] = r[j++];  
            else rf[k] = r[i++];  
        }  
        while(i <= m)  rf[k++] = r[i++];  
        while(j <= n)  rf[k++] = r[j++];  
        print(rf,n+1);  
    }  
      
    void MergeSort(ElemType *r, ElemType *rf, int lenght)  
    {   
        int len = 1;  
        ElemType *q = r ;  
        ElemType *tmp ;  
        while(len < lenght) {  
            int s = len;  
            len = 2 * s ;  
            int i = 0;  
            while(i+ len <lenght){  
                Merge(q, rf,  i, i+ s-1, i+ len-1 ); //对等长的两个子表合并  
                i = i+ len;  
            }  
            if(i + s < lenght){  
                Merge(q, rf,  i, i+ s -1, lenght -1); //对不等长的两个子表合并  
            }  
            tmp = q; q = rf; rf = tmp; //交换q,rf,以保证下一趟归并时,仍从q 归并到rf  
        }  
    }  
      
      
    int main(){  
        int a[10] = {3,1,5,7,2,4,9,6,10,8};  
        int b[10];  
        MergeSort(a, b, 10);  
        print(b,10);  
        cout<<"结果:";  
        print(a,10);  
      
    }

    两路归并的递归算法

    void MSort(ElemType *r, ElemType *rf,int s, int t)  
    {   
        ElemType *rf2;  
        if(s==t) r[s] = rf[s];  
        else  
        {   
            int m=(s+t)/2;          /*平分*p 表*/  
            MSort(r, rf2, s, m);        /*递归地将p[s…m]归并为有序的p2[s…m]*/  
            MSort(r, rf2, m+1, t);      /*递归地将p[m+1…t]归并为有序的p2[m+1…t]*/  
            Merge(rf2, rf, s, m+1,t);   /*将p2[s…m]和p2[m+1…t]归并到p1[s…t]*/  
        }  
    }  
    void MergeSort_recursive(ElemType *r, ElemType *rf, int n)  
    {   /*对顺序表*p 作归并排序*/  
        MSort(r, rf,0, n-1);  
    }


0 +1

版权声明

 Java  源码  算法

 请文明留言

0 条评论