利用非递归方式实现二路归并

布满荆棘的人生 2023-02-17 15:00 11阅读 0赞

## 又是被大作业支配的恐惧 ##

![在这里插入图片描述][20200614210123369.png]

## 代码 ##

#include<bits/stdc++.h>
    using namespace std;
    
    void Merge(int r[],int r1[],int s,int m,int t)
    { 
        int i=s,j=m+1,k=s;
        while(i<=m&&j<=t)
        { 
            if(r[i]<=r[j])
            { 
                r1[k]=r[i];
                i++;
                k++;
            }
            else
            { 
                r1[k]=r[j];
                j++;
                k++;
            }
        }
        if(i<=m)
        { 
            while(i<=m)
            { 
                r1[k]=r[i];
                i++;
                k++;
            }
        }
        else
        { 
            while(j<=t)
            { 
                r1[k]=r[j];
                j++;
                k++;
            }
        }
    }
    
    void MergePass(int r[] ,int r1[] , int n, int h)
    { 
        int i=1;
        while(i<=n-2*h+1)
        { 
            Merge(r,r1,i,i+h-1,i+2*h-1);
            i+=2*h;
        }
        if(i<n-h+1) Merge(r,r1,i,i+h-1,n);
        else for(int k=i; k<=n; k++)
        { 
            r1[k]=r[k];
        }
    }
    
    void MergeSort(int r[],int r1[], int n)
    { 
        int h=1;
        while(h<n)
        { 
            MergePass(r,r1,n,h);
            h*=2;
            MergePass(r1,r,n,h);
            h*=2;
        }
    }
    
    int main()
    { 
        int a[10000];
        int a1[10000];
        int n=0;
        cout<<"请输入生成随机数的数量 n，(100<n<10000)" <<endl;
        
        do{ 
        	cin>>n;
        	if(n<=100||n>10000)
        		cout<<"n不属于(100,10000),请重新输入随机数的数量 n"<<endl; 
        }while(n<=100||n>10000);
        int sj=0,xj=0; 
        cout<<"请输入生成随机数的范围，包含两个数字 [下界，上届] n" <<endl;
        cin>>xj>>sj;
        for(int i=1;i<=n;i++) a[i]=(rand() % (sj-xj+1))+ xj;
        MergeSort(a,a1,n);
        for(int i=1;i<=n;i++) cout<<a[i]<<" ";
        cout<<endl;
        return 0;
    }

[20200614210123369.png]: https://img-blog.csdnimg.cn/20200614210123369.png