VC驿站

 找回密码
 加入驿站

QQ登录

只需一步,快速开始

搜索
查看: 443|回复: 5

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

[复制链接]
06_avatar_middle
最佳答案
0 
在线会员 发表于 2021-12-10 16:22:28 | 显示全部楼层 |阅读模式
//是这自己按理解写的,迭代算法,运行很慢。觉的比高手慢一点可以理解,但慢很多倍就搞不懂了

#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;
}




上一篇:求助!MFC对话框项目中,如何使工具栏与菜单栏出现在同一行?
下一篇:家谱管理
00_avatar_middle
最佳答案
12 
在线会员 发表于 2021-12-11 08:27:25 | 显示全部楼层
打破零回复
水平有限看不出来什么问题
讲点题外话
你和高手的电脑配置一模一样吗
内存大小 内存频率  cpu型号  CPU主频   硬盘读写速度.....
操作系统版本 ide环境
为什么我写的归并算法这么慢,帮看看问题所在


83_avatar_middle
最佳答案
0 
在线会员 发表于 2021-12-11 11:26:11 | 显示全部楼层
看着太难受了,还不如截屏图片看起来舒服,哥。
17_avatar_middle
最佳答案
39 
在线会员 发表于 2021-12-11 13:11:52 | 显示全部楼层
本帖最后由 yoobaby 于 2021-12-11 13:13 编辑

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

O(n^2),以上的复杂度都得慢!

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

评分

参与人数 1驿站币 +1 热心值 +1 收起 理由
00_avatar_small oyxbl + 1 + 1 靠谱

查看全部评分

06_avatar_middle
最佳答案
0 
ico_lz  楼主| 发表于 2021-12-11 18:53:41 | 显示全部楼层
yoobaby 发表于 2021-12-11 13:11
代码没细看:你这各种循环。然后gbsplit1还又调用myswap里面又是循环,时间复杂度太高了。

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

是先分割,然后排序,然后重复这个过程 直到 f==0 ,对最后一组进行排序。。
06_avatar_middle
最佳答案
0 
ico_lz  楼主| 发表于 2021-12-14 22:36:20 | 显示全部楼层
问一下,这个归并是怎么理解的,想不明白为什么他速度会快我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;

}
您需要登录后才可以回帖 登录 | 加入驿站 qq_login

本版积分规则

×【发帖 友情提示】
1、请回复有意义的内容,请勿恶意灌水;
2、纯数字、字母、表情等无意义的内容系统将自动删除;
3、若正常回复后帖子被自动删除,为系统误删的情况,请重新回复其他正常内容或等待管理员审核通过后会自动发布;
4、感谢您对VC驿站一如既往的支持,谢谢合作!

关闭

站长提醒上一条 /2 下一条

QQ|小黑屋|手机版|VC驿站 ( 辽ICP备09019393号-4 )|网站地图wx_jqr

GMT+8, 2022-12-10 02:42

Powered by CcTry.CoM

© 2009-2021 cctry.com

快速回复 返回顶部 返回列表