归并排序——二路归并排序

分手后的思念是犯贱 2022-03-20 02:54 358阅读 0赞

/*
     *归并：
     *  指将两个或者两个以上的有序表合并成一个新的有序表
     *
     *二路归并算法思想：
     *  将长度为n的待排序数据表看成是n个长度为1的有序表，并将这些有序表两两归并，
     *  便得到[n/2]个有序表；再将这[n/2]个有序表两两归并，如此反复，直到最后得到
     *  长度为n的有序表为止。
     */
    
    /*
     *过程分析：
     *  若有序表A、B同属于一个数据表R，是R的两个有序区，并且R[low]~R[mid]为有序表A
     *  的存储区，R[mid+1]~R[high]为有序表的存储区。将其归并成为一个有序表C，存放在
     *  R1中，进行的算法描述如Merge(int R[],int R1[],int low,int mid,int high)函数。
     *
     *  在分析二路归并算法实现之前，首先分析一趟归并问题。假设待排序序列的长度为n，
     *  一趟归并时可能有3种情况。
     *      1.该趟归并前，R中参与归并的两个有序表的长度均为len
     *          这时相邻的两个有序表的下标范围是(i~i+len-1)和(i+len~i+len*2-1)。则调用为
     *              Merge(R,R1,i,i+len-1,i+len*2-1)
     *      2.最后一对参与归并的有序表中，其中一个长度小于len
     *          即i+len<n-1且i+len*2-1>n-1。也就是说最后一个有序表中最后一个元素的下标为n-1
     *          此时的调用为
     *              Merge(R,R1,i,i+len-1,n-1);
     *      3.参与归并的最后只剩下一个有序表R
     *          即i+len-1>n-1，则只需要把有序表R直接复制到R1中即可
     *
     *  二路归并的一趟归并的算法：
     *      对无序表进行二路归并就是调用上述一趟归并算法，对待排序序列进行若干趟归并。第一趟
     *      归并时，每个有序表的长度为1，即len=1,。归并后有序表的长度len就扩大一倍。即排序中len
     *      从1,2,4，……到[n/2]，可以用while循环实现整个归并过程
     */
    
    /*
     *性能分析：
     *  时间复杂度是O(nlog2n).空间复杂度是O(n)
     */
    #include <stdio.h>
    #define length 9
    
    void Merge(int R[],int R1[],int low,int mid,int high)
    {
        int i=low,j=mid+1,k=low;
        while(i<=mid && j<=high)//需要两个条件同时成立，因为两个序列的长度可能不一样
        {
            if(R[i]<=R[j])
            {
                R1[k]=R[i];
                ++i;
            }
            else
            {
                R1[k]=R[j];
                ++j;
            }
            ++k;
        }
        while(i<=mid)R1[k++]=R[i++];
        while(j<=high)R1[k++]=R[j++];
    }
    void MergePass(int R[],int R1[],int len)//进行一次归并排序
    {
        int j,i=0;
        while(i+len*2<=length)
        {
            Merge(R,R1,i,i+len-1,i+len*2-1);
            i=i+len*2;
        }
        if(i+len-1<length-1)Merge(R,R1,i,i+len-1,length-1);
        else
            for(j=i;j<length;j++)R1[j]=R[j];
    }
    void MergeSort(int *order)
    {
        int len=1;
        int *R1;
        R1=(int *)malloc(sizeof(int)*length);
        while(len<=(length/2+1))
        {
            MergePass(order,R1,len);
            len=2*len;
            MergePass(R1,order,len);//两次归并后，结果仍在order中
            len=2*len;
        }
        free(R1);
    }
    
    int main()
    {
        int order[length]={0,49,52,65,97,35,13,27,49};
        MergeSort(order);
        int i;
        for(i=0;i<length;i++)printf("%d  ",order[i]);
        return 0;
    }