c - 合并排序三个子 vector

Question

我正在做一个合并排序的版本，它不是将 vector 划分为两个子 vector ，而是将数组划分为3个子 vector ，只是我在这篇论文中遇到了问题，算法只正确于程序关闭，我可以帮忙，请按照下面的代码进行查看:

void Intercala(int v[],int inicio,int meio1,int meio2,int fim)
{
int i,j,k,*w;
w=(int*)malloc((fim-inicio)*sizeof(int));
i=inicio;
j=meio1;
l=meio2;
k=0;
while(i<meio1&&j<meio2)
{
    if(v[i]<=v[j])
        w[k++]=v[i++];
    else
        w[k++]=v[j++];
}
while(l<fim)
{
    w[k++]=v[l++];

}
while(i<meio1)
    w[k++]=v[i++];
while(j<meio2)
    w[k++]=v[j++];
while(l<fim)
    w[k++]=v[l++];
for(i=inicio;i<fim;i++)
    v[i]=w[i-inicio];
free(w);        
}
void Merge_Sort(int v[],int inicio,int fim)
{
int meio1,meio2;
if(inicio<fim-1)
{
    meio1=(inicio+fim)/3;
    meio2=meio1*2;
    Merge_Sort(v,inicio,meio1);
    Merge_Sort(v,meio1,meio2);
    Merge_Sort(v,meio2,fim);
    Intercala(v,inicio,meio1,meio2,fim);
}
}

Answer 1

Merge sort是一种分而治之的算法。在标准实现中，首先将列表拆分为两个子列表，对这两个列表进行递归排序，然后将这两个已排序列表合并为一个已排序列表。

对于三个子 vector ，这是完全相同的事情，只是您需要调整分割和合并逻辑以处理三个 vector 而不是两个 vector 。从较高的层次来看，它应该看起来像这样:

void merge_sort(int v[], int len)
{
    /* Code to handle the base case (lists of length 1) */
    /* ... */

    /* v1-v3, len1-len3 are out parameters */
    divide(v, v1, &len1, v2, len2, v3, len3);

    merge_sort(v1, len1);
    merge_sort(v2, len2);
    merge_sort(v3, len3);

    merge(v, len, v1, len1, v2, len2, v3, len3);
}

不幸的是，我不会说代码最初编写的语言，因此我无法理解代码的初衷，但我的一些问题/建议包括:

• 您是否正确处理了基本情况？
• 为什么Intercala()要动态分配额外的内存？这在合并排序中不是必需的，因为合并排序可以就地工作。
• 这个问题非常适合单元测试——对于任何输入，您都可以轻松确定输出。因此，考虑为 Intercala() 编写一些单元测试，看看它是否适用于您能想到的所有情况。一旦您知道 Intercala() 可以工作，请考虑为整个 Merge_Sort() 算法编写单元测试。

祝你好运!