黑马程序员技术交流社区

标题: 有人懂归并排序吗？ [打印本页]
作者: absvir    时间: 2016-8-18 18:55
标题: 有人懂归并排序吗？
好奇自己写了个归并排序，断断续续折腾几天终于成功了，结果测试速度，发现比冒泡还慢。无语了！！！我推测估计是递归太多，有反复创建集合而拖慢了速度，但真的不好优化啊，就算改用数组，合并两个序列也免不了创建数组，而冒泡一直在一个数组内操作，这先天就比不了啊。
作者: zztierlie    时间: 2016-8-18 19:13
数据量太小导致的，数据量大点就显示出来了
作者: absvir    时间: 2016-8-18 19:54
zztierlie 发表于 2016-8-18 19:13
数据量太小导致的，数据量大点就显示出来了

测试使用了随机生成的10万个整数，冒泡排序时间在50ms以内，归并都在1000ms以上。根据我搜索的结果，我估计应该是我归并代码的问题。
作者: abcdefg11    时间: 2016-8-18 21:19
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;
        }       
}
大概想了下应该是这样？
作者: absvir    时间: 2016-8-18 22:29
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
absvir 发表于 2016-8-18 22:29
不知道你有没有测试你的代码,我感觉你的代码是运行不出结果的.
1.count变量被初始化为0,而接下来的while ...

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

明天我琢磨一下，{:3_57:}{:3_57:}{:3_57:}
作者: abcdefg11    时间: 2016-8-19 12:52
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里就完成了，因为我看了别人的代码我就不写了。




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2