设子数组a[0:k]和a[k+1:n-1]已排序好(0<=k<=n-1).试设计一个合并这两个
设子数组a[0:k]和a[k+1:n-1]已排序好(0<=k<=n-1).试设计一个合并这两个
子数组为排序的数组a[0:n-1]的算法。要求算法在最坏情况下所用时间为O
(n),且只用到O(1)的辅助空间。
问题点数：7、回复次数：7Top
1 楼booming（信誉值由于系统错误导致）回复于 2005-07-24 14:30:56 得分 0
upTop
2 楼xiaoxiaofei（小小飞）回复于 2005-07-25 09:36:39 得分 0
晕，还发两个帖子。。。。。。
都说了，这个必须有一个c【n】数组的，不然没法存放数据啊！！Top
3 楼booming（信誉值由于系统错误导致）回复于 2005-07-27 15:30:58 得分 0
我给个程序，你可以帮我举一个使他运行错误的例子吗？谢谢。因为我无法证明它正确。
#include <stdio.h>
#define N 14
#define K 10
int a[N]={1,2,3,4,6,8,10,11,12,13,14,-10,-9,16};
//测试数据
/*{ 5,100,101,1,2,2,4,6,8,10,100,101,120};
{1,2,3,4,6,8,10,11,12,13,14,-10,-9,16};
{1,2,3,4,6,8,10,11,12,13,14,-10,-9,16};
{1,3,5,7,9,2,4,6,8,10};
{ 5,100,101,1,2,4,5,100,101,120};
{ 5,100,101,1,2,2,4,6,8,10,100,101,120};
*/
//把a[k]后的元素与前面子数组元素交换，插到合适位置。
void f(int a[],int k,int n)//排序a[0:k]和a[k+1:n-1]
{int i,j,tmp,t,i0;j=k+1;i0=k+1;t=i0;
for(i=0;i<j;i++)
{
if(i==i0)
{
i0=j;
if(t==i)//t不为i时候，已经指向i0和j之间小的元素了
{//t始终指向i0和j之间小的元素
if(a[j]<a[i+1]) t=j;
else t=i+1;
}
}
if(a[t]<a[j])
{
if(a[i]>a[t])
{tmp=a[t];a[t]=a[i];a[i]=tmp; t++;
if(t==j) t=i0;
}
}
else if(a[i]>a[j]){ tmp=a[j];a[j]=a[i];a[i]=tmp;j++;}
else if(j!=i0&&a[i]>a[t])
{
tmp=a[t];a[t]=a[i];a[i]=tmp;t++;
if(t==j) t=i0;
}
}//for
}//2.12
void main()
{
f(a,K,N);
for(int i=0;i<N;i++)
printf("%d,",a[i]);
}Top
4 楼xiaoxiaofei（小小飞）回复于 2005-07-27 16:15:18 得分 7
你这个是‘一个’数组里的元素，根本不是什么‘两个子数组’。
如果是书上的原话，那么就是垃圾出版社和编辑弄错了。Top
5 楼xiaoxiaofei（小小飞）回复于 2005-07-27 16:16:10 得分 0
同一个数组这种问题自己搞定，没一点挑战性Top
6 楼booming（信誉值由于系统错误导致）回复于 2005-07-27 20:34:01 得分 0
我不会啊。你能用分治法做下啊。谢谢了。Top
7 楼booming（信誉值由于系统错误导致）回复于 2005-07-29 11:08:08 得分 0
upTop
