n个已排序的数组进行合并，合并后的数组也是有序的，有没有什么比较好的算法，最好有个例子

发布网友 发布时间：2022-05-16 05:13

我来回答

共4个回答

热心网友 时间：2023-10-12 03:45

假设n个有序（递增排序）数组A1...An，第i个数组元素下标从0到leni-1
那么执行代码如下进行合并：
【1】求VMAX = max{A1[len1-1], A2[len2-1], ... An[lenn-1]}; //即求所有数组最大值
A1[len1] = A2[len2] = ... = An[lenn] = VMAX; //让每个数组末尾都填入一个最大值，做哨兵使用
【2】int index[MAX_SIZE] = {0}; //初始化每个数组的指标
while (not_end())
step();
其中not_end函数判断是否A1<len1 && A2<len2 && ... && An<lenn //用循环，容易实现
作为while的结束条件
step()进行合并的每一步操作，首先依据index指示的每个数组当前位置，选取最小元素及其对应指标，将最小元素插入新数组末尾，将对应指标后移。

如果两个数组合并会的话，理解这个很简单。 复杂度是o(len1+len2+...+lenn)
当然先合并两个，再合并两个，不断下去，也可以，不过复杂度较上面那个高

热心网友 时间：2023-10-12 03:45

两个已排序数组p和q，假设将他俩合成一个有序数组，首先可以明确的是，不要幻想真的把p和q合并成一个新的有序数组

热心网友 时间：2023-10-12 03:46

归并排序：

#include <stdio.h>
#include <stdlib.h>
typedef int datatype;
datatype *dst(datatype *a,const size_t na,datatype *b, const size_t nb,datatype *c)
{
size_t k=0,i=0,j=0;
datatype *cc=(datatype*)malloc(sizeof(datatype)*(na+nb));
while (i<na&&j<nb)
{
if (a[i]<b[j]) cc[k++]=a[i++];
else cc[k++]=b[j++];
}
while (i<na)
cc[k++]=a[i++];
while (j<nb)
cc[k++]=b[j++];
for (i=0;i<na+nb;i++)
c[i]=cc[i];
free(cc);
return c;
}
void prt(datatype *ar,size_t n)
{
size_t i;
for (i=0;i<n;i++)
printf("%d ",ar[i]);
putchar('\n');
}
int main(int argc,char *argv[])
{
datatype a[]={1,3,5,7,9},
b[]={0,2,4,6,8,10},
c[]={11,13,15,17,19},
d[]={12,14,16,18,20},
e[21];
prt(dst(e,0,a,5,e),5);
prt(dst(e,5,b,6,e),11);
prt(dst(e,11,c,5,e),16);
prt(dst(e,16,d,5,e),21);
return 0;
}

热心网友 时间：2023-10-12 03:46

这不就是多路归并排序么？
看看归并排序