A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

© absvir 中级黑马   /  2016-8-18 18:55  /  904 人查看  /  6 人回复  /   0 人收藏 转载请遵从CC协议 禁止商业使用本文

好奇自己写了个归并排序,断断续续折腾几天终于成功了,结果测试速度,发现比冒泡还慢。无语了!!!我推测估计是递归太多,有反复创建集合而拖慢了速度,但真的不好优化啊,就算改用数组,合并两个序列也免不了创建数组,而冒泡一直在一个数组内操作,这先天就比不了啊。

6 个回复

倒序浏览
数据量太小导致的,数据量大点就显示出来了
回复 使用道具 举报
zztierlie 发表于 2016-8-18 19:13
数据量太小导致的,数据量大点就显示出来了

测试使用了随机生成的10万个整数,冒泡排序时间在50ms以内,归并都在1000ms以上。根据我搜索的结果,我估计应该是我归并代码的问题。
回复 使用道具 举报
a=int[1000]//待排序数组
b=int[1000]
int count=0;
int j=0;
while(count!=0){
for(int=0;i<=499;i++){
        if(a[i]>a[i+500]){
                b[j]=a[i+500];
                b[j+1]=a[i];
                j+=2;
                count++;
                continue;
        }else{
                b[j]=a[i];
                b[j+1]=a[i+500]
                j+=2;
                count++;
                continue;
        }
        if(i=499){
                a=b;
                j=0;
        }       
}
大概想了下应该是这样?
回复 使用道具 举报
abcdefg11 发表于 2016-8-18 21:19
a=int[1000]//待排序数组
b=int[1000]
int count=0;

不知道你有没有测试你的代码,我感觉你的代码是运行不出结果的.
1.count变量被初始化为0,而接下来的while循环却必须count!=0时才会执行,而count++语句在while循环里,也就是count的值永远为0,且不会被改变,while循环不会被执行
2.最后一个if(i=499)是什么意思?你发的代码中只有for循环声明了一个i,但是,这个i的作用于只在for循环内吧,for之外的if是怎么访问并判断的?

代码没加注释,所以理解你的思路有点困难.我理解的你是想,把数组a左边和对应的下标的元素比较并存入数组中.如果你是这个思路的话,那么你对归并排序的理解有误.原理太长不码字了,举个例子吧,左边数组1,2,3右边数组4,5,6按你的代码思路,最后数组b排序结果是1,4,2,5,3,6

正确归并思路应该是,1<4,所以数组b放1;然后2<4;数组b在放2;3<4,数组b在放3;最后左边没数字了,又因为两个子数组都是有序的,直接把4,5,6放进数组b
回复 使用道具 举报
abcdefg11 来自手机 中级黑马 2016-8-19 00:54:29
地板
absvir 发表于 2016-8-18 22:29
不知道你有没有测试你的代码,我感觉你的代码是运行不出结果的.
1.count变量被初始化为0,而接下来的while ...

好认真的回复,我没测试,睡不着想了想这个代码是有问题的

明天我琢磨一下,{:3_57:}{:3_57:}{:3_57:}
回复 使用道具 举报
abcdefg11 来自手机 中级黑马 2016-8-19 12:52:33
7#
absvir 发表于 2016-8-18 22:29
不知道你有没有测试你的代码,我感觉你的代码是运行不出结果的.
1.count变量被初始化为0,而接下来的while ...

太遗憾了我表示我不用递归失败了,最后还是看了老师的代码,传递同一个数组,然后将分离点比如正中间当做参数传递过去,temp数组只按参数设定的比如1到mid范围赋值

比如void mSort(in[]arr,int[]temp,int a,int b)
arr是待排序数组,temp是临时数组,a到b是分割的范围,temp在赋值时只赋值tempa~temb这样
接着再分temp,a~b,判断完了加到arr里就完成了,因为我看了别人的代码我就不写了。
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马