为什么我写的归并算法这么慢，帮看看问题所在

xiethree

//是这自己按理解写的，迭代算法，运行很慢。觉的比高手慢一点可以理解，但慢很多倍就搞不懂了

#include <iostream>
#include <cstdlib>
using namespace std;
void myswap(int*,int*,const int&,const int&);
void gbsplit1();
int main(){

    gbsplit1();
    return 0;
}
void gbsplit1(){
    const int maxnum=10000000;
        int *s=new int[maxnum];
    int num=maxnum;
        for(int i=0;i<maxnum;i++)
        s[i]=rand()% maxnum;

        int step=1;         //步长为1
        int f=num/2;        //初始组数
        int* a=s;
    int* b=s;
    int j=0;

    while(f !=0){
        //先根据组数进行排序
        for(int i=0;i<f;i++){
            myswap(a+j,b+j+step,step,step);
            j=j+step+step;
        }

        //对剩下进行排序(如果有的话)
                if(num-j>0){
                        num=num-j;
                        while(num>step){
                                num=num-step;
                                if(num>0){
                                        myswap(a+j,b+j+step,step,num);
                                }
                        }
                }

        step=step*2;    //步长增加
        f=f/2;
        j=0;
        num=maxnum;
    }

       //把最后两组组成一组
       num=num-step;   
        myswap(a+j,b+j+step,step,num);
/*
        for(int i=0;i<maxnum;i++){
        cout<<s[i]<<"  ";
        }
        cout<<endl;
*/
        delete []s;
}

void myswap(int *a,int *b,const int& num1,const int& num2){
    if(a[num1-1]<= b[0])   //如果是已经从小到大排序好的
        return;             //直接跳出
    else if(a[0]>= b[num2-1]){
        int *c=new int[num1];
        for(int i=0;i<num1;i++){
            c[i]=a[i];
        }
        for(int i=0;i<num2;i++){
            a[i]=b[i];
        }
        for(int i=0,j=num2;i<num1;i++,j++){
            a[j]=c[i];
        }
        return;
    }

    int *c=new int[num1 +num2];
        int i=0;        //指向a数组下标
        int j=0;        //指向b数组下标
        int k=0;        //指向c数组下标

        while(i<num1 && j<num2){  //只要i且j同时小于各自数组元素大小
        if(a[i]>=b[j]){     //把小的数加入到c数组
            c[k]=b[j];
            j++;
        }else{
            c[k]=a[i];
            i++;
        }
        k++;                //指向下一位c数组元素下标
        }

        if(i>=num1){         //如果是从i出来，必须把b数组剩余元素加到c数组
        for(int z=j;z<num2;z++){//必须从j这个位置加起，而不能是j+1位置开始
            c[k]=b[z];
            k++;
        }
        }else{              //否则是从j出来,则必须把a数组剩余元素加到c数组
        for(int z=i;z<num1;z++){
            c[k]=a[z];
            k++;
        }
        }

        for(int i=0;i<num1 +num2;i++)    //把临时数组复制到原数组
              a[i]=c[i];
    delete []c;
}

oyxbl

打破零回复
水平有限看不出来什么问题
讲点题外话
你和高手的电脑配置一模一样吗
内存大小 内存频率  cpu型号  CPU主频   硬盘读写速度.....
操作系统版本 ide环境

crlong33

看着太难受了，还不如截屏图片看起来舒服，哥。

yoobaby

代码没细看：你这各种循环。然后gbsplit1还又调用myswap里面又是循环，时间复杂度太高了。

O(n^2)，以上的复杂度都得慢！

你去了解下算法的时间复杂度，然后再改改看！你就知道这种写法为什么会慢了！

xiethree

yoobaby 发表于 2021-12-11 13:11
代码没细看：你这各种循环。然后gbsplit1还又调用myswap里面又是循环，时间复杂度太高了。

O(n^2)，以上 ...

是先分割，然后排序，然后重复这个过程 直到 f==0 ，对最后一组进行排序。。

xiethree

问一下，这个归并是怎么理解的，想不明白为什么他速度会快我10倍？1E 个数据，我40几秒，他才4秒。。。

void merge_sort(int*a,int num){
    int left_min,left_max,right_min,right_max,index;
    int temp[num]={};
    for(int i=1;i<num;i*=2){//结束条件i<num因为这个循环的意义是i个数据一组和另一个i个数据组比较
    //比较完后得到一个有序的i*2个数据组,所以i相当于一个数据组的长度,如果i<=num了,那下次循环
     //就是num个数据和另一num个数据组比较,可总共就num个数据,所以逻辑错误了
        for(left_min=0;left_min<num-i;left_min=right_max){
        //这个结束条件是left_min<num-i因为,left_min<num-i相当于left_min+i<num
         //就是right_min<num,right_min是右边数据的第一个元素,它至少也要在a数组的最后一个元素上
         //即num-1,如果它>=num了,就等于没有右边的数据,只有左边的数据了,那就没必要再比较了,所以这时候退出
            left_max=right_min=left_min+i;
            right_max=right_min+i;//left_max和right_max指向的不是他们数据组中最后一个元素
                                  //而是最后一个的下一个元素,是无法到达的
            if(right_max>num)
                right_max=num;//right_max最大也只能是指向num
            index=0;
            while(left_min<left_max && right_min<right_max){
                if(a[left_min]<=a[right_min]){
                    temp[index]=a[left_min];
                    left_min++;
                }else{
                    temp[index]=a[right_min];
                    right_min++;
                }
                index++;
            }
            while(left_min<left_max){
                --right_min;
                --left_max;
                a[right_min]=a[left_max];
            }
            //发现了只检查左部分有没有比较完,其实不用检查右部分,
            //因为退出循环的时,就算右半部分没比较完,但它一定是比较的两组中值最大的几个,
            //且一定是排好序的,它们已经在合适的位置上
            while(index>0){
                --right_min;
                --index;
                a[right_min]=temp[index];//将temp数据重分配,注意一定要是--right_min
            }
        }
    }
}

int main(){
    int a[]={9,1,2,8,1,6,8,5,0,-1};
    const int maxint=10;
    merge_sort(a,maxint);

  return 0;

}