| 网站首页 | 业界新闻 | 小组 | 威客 | 人才 | 下载频道 | 博客 | 代码贴 | 在线编程 | 编程论坛
欢迎加入我们,一同切磋技术
用户名:   
 
密 码:  
共有 4239 人关注过本帖
标题:[求]两数组合并成一个有序数组的最佳算法
只看楼主 加入收藏
hijk_12
Rank: 1
等 级:新手上路
帖 子:47
专家分:0
注 册:2005-6-25
收藏
 问题点数:0 回复次数:7 
[求]两数组合并成一个有序数组的最佳算法
这是一条二级C++的题目,本人已经做出来了,但其方法觉得麻烦(就是先将两个数组复制到数组C中,然后用冒泡排序方法使 C数级变成一个有序数组)

完成void fun()函数,其功能是:将两个有序数组A和B,复制合并出一个有序整数序列C,其中形参n和m分别是数组A和B的元素个数.
#include<iostream>
using namespace std;

void fun(int a[],int n, int b[],int m, int *c)
{
}

int main()
{
int A[]={1,3,5,7,9,11,18,32};
int B[]={5,15,19,21,23};
int C[25];

for(int i=0;i<25;i++) C[i]=0;
fun(A,sizeof(A)/sizeof(int),B,sizeof(B)/sizeof(int),C);

return 0;
}
搜索更多相关主题的帖子: 算法 void fun std 
2006-02-09 10:05
ElfDN
Rank: 4
等 级:贵宾
威 望:11
帖 子:291
专家分:0
注 册:2005-11-13
收藏
得分:0 
笨。。。。。。
已经是有序的就该好好利用
我模板库里有一个
//merge
#include<iostream>
using namespace std;
//input:2arrays a,b;a,b sorted;
int main(){
int a[9]={1,4,5,9,10,12,15,22,35},b[5]={7,8,23,27,32},c[14];
for(int ai=0,bi=0,ci=0; ci<14; ci++){
if(bi>=5||a[ai]<b[bi])
c[ci]=a[ai++];
else if(ai>=9||a[ai]>b[bi])
c[ci]=b[bi++];
cout<<c[ci]<<" ";
}
cout<<endl;
}

2006-02-09 10:24
aiyuheng
Rank: 1
等 级:新手上路
威 望:1
帖 子:656
专家分:0
注 册:2006-1-12
收藏
得分:0 

可以A和B的元素先比较 然后在放进C
不过我不知道这样算不算好的算法


when i want to ask anyone,i will ask myself first.
2006-02-09 10:31
ElfDN
Rank: 4
等 级:贵宾
威 望:11
帖 子:291
专家分:0
注 册:2005-11-13
收藏
得分:0 
用冒泡是O(n^2)的算法,合并是O(n)的算法。到了高阶,合并只是一个子算法,也就只相当一个函数,一个函数的质量好坏相差就大得多了,不过2级嘛,随便你怎么搞好了,要能这样超时,超内存也难的

2006-02-09 10:38
hijk_12
Rank: 1
等 级:新手上路
帖 子:47
专家分:0
注 册:2005-6-25
收藏
得分:0 

嗯,明白,多谢版主指点迷津.


2006-02-09 11:51
woodhead
Rank: 3Rank: 3
等 级:新手上路
威 望:9
帖 子:1124
专家分:0
注 册:2005-7-18
收藏
得分:0 

才发现elfdn的算法不太对劲, 改一下条件,结果就不对了.

#include<iostream>
using namespace std;
//input:2arrays a,b;a,b sorted;
int main(){
{
int x[100]={0};
}

int a[9]={1,4,5,9,10,12,15,22,35},b[5]={7,8,23,27,50},c[14];
for(int ai=0,bi=0,ci=0; ci<14; ci++){
if(bi>=5||a[ai]<b[bi])
c[ci]=a[ai++];
else if(ai>=9||a[ai]>b[bi])
c[ci]=b[bi++];
cout<<c[ci]<<" ";
}
cout<<endl;
system("pause");
}

你选的正好短数组的最大值比长数组最大值小,也就是短的先比完了,我改了一下,改成50了,这样运行时数组a[]就越界了,结果要看内存中那块地址中的值是多少了


2006-03-10 18:24
ElfDN
Rank: 4
等 级:贵宾
威 望:11
帖 子:291
专家分:0
注 册:2005-11-13
收藏
得分:0 

#include<iostream>
using namespace std;
//input:2arrays a,b;a,b sorted;
int main(){
int a[9]={1,4,5,9,10,12,15,22,35},b[5]={7,8,23,27,50},c[14];
for(int ai=0,bi=0,ci=0; ci<14; ci++){
if(bi>=5||a[ai]<b[bi]&&ai<9)
c[ci]=a[ai++];
else if(ai>=9||a[ai]>b[bi]&&bi<5)
c[ci]=b[bi++];
cout<<c[ci]<<" ";
}
cout<<endl;
system("pause");
}
//呵呵,谢谢woodhead帮忙找的BUG,因为库里的东西都是自己写的,有BUG也不容易检查,总之谢谢拉


2006-03-11 05:17
woodhead
Rank: 3Rank: 3
等 级:新手上路
威 望:9
帖 子:1124
专家分:0
注 册:2005-7-18
收藏
得分:0 

2006-03-11 13:20
快速回复:[求]两数组合并成一个有序数组的最佳算法
数据加载中...
 
   



关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有,并保留所有权利。
Powered by Discuz, Processed in 0.059748 second(s), 9 queries.
Copyright©2004-2024, BCCN.NET, All Rights Reserved