这段代码中的东西的纬度是丰富的。有些是阻碍,但最终它是您的合并功能。典型的合并算法在每次迭代时将一个项目移动到目标缓冲区,直到一个列表或另一个列表用尽。一旦发生这种情况,剩余列表中的剩余项目将被批量复制到位并且算法终止。
你有一个根本性的缺陷,我们现在将介绍它。您的主循环k
一直运行到n
,至少这是正确的。但是,请查看 if-else-if 条件中的第一个表达式:
if((i<mid)&&(j>= n))
{
memcpy(temp+(k*size), a+i*size, size);
i++;
}
else if((i<mid)&&(fcmp(a + i*size, a+j*size) <= 0))
{
memcpy(temp+(k*size), a+j*size, size);
j++;
}
他们都有,i<mid
所以这可以简化为:
if (i<mid)
{
if (j>=n)
{
memcpy(temp+(k*size), a+i*size, size);
i++;
}
else if (fcmp(a + i*size, a+j*size) <= 0))
{
memcpy(temp+(k*size), a+j*size, size);
j++;
}
}
这意味着如果您的i
-side在您的-side之前已经用尽,那么您从那时起什么也不j
做,只是递增直到达到. 拆分列表的 -side 的其余部分被完全忽略。然后,在函数结束时,将未初始化的数据复制到原始数组的顶部。k
n
j
有些事情要考虑。首先,输入您的比较器功能要求并坚持下去。比较器有责任遵守回调请求者的要求;不是相反。
typedef int (*fn_cmp)(const void*, const void*);
并通过实现对该标准的回调来正确使用它。
// compare two nodes.
int compare_node(const void* lhs, const void* rhs)
{
const node* lhn = lhs;
const node* rhn = rhs;
return (strcmp(lhn->name, rhn->name));
}
这也使您的通用合并排序更加清晰:
// generic mergesort algorithm
void genmsort(void *src, unsigned int len, unsigned int size, fn_cmp fcmp)
{
if (len < 2)
return;
unsigned int mid = len/2;
genmsort(src, mid, size, fcmp);
genmsort((unsigned char*)src+(mid*size), len - mid, size, fcmp);
merge(src, mid, len-mid, size, fcmp);
}
除了可读性之外,以下内容与您的最大区别是添加了第二个长度参数(这个有效merge
的事实被认为是一个奖励)。您的代码从最初传入的单个长度推断出这个值;在计算递归分区大小时,您在代码中完全独立的位置执行的操作这些相同的大小也需要在此处传递,原因有多种,包括一致性和可用性)。
请考虑以下问题。如果可以更好地注释这个算法,或者让它更清晰,我不知道如何:
// merges two lists back to back in a single sequence.
void merge(void *src,
unsigned int alen, // note parition size.
unsigned int blen, // and again here.
unsigned int size,
fn_cmp fcmp)
{
void *bsrc = (unsigned char*)src + alen * size;
void *dst = malloc((alen + blen)*size);
unsigned int a = 0, b = 0, k = 0;
for (k=0; k<(alen+blen); ++k)
{
// still got a's ?
if (a < alen)
{
// still got b's ?
if (b < blen)
{
// get "lesser" of the two.
if (fcmp((const unsigned char*)src + a*size,
(const unsigned char*)bsrc + b*size) <= 0)
{
// a is less. move it in.
memcpy((unsigned char *)dst + k*size,
(const unsigned char*)src + a++*size, size);
}
else
{ // b is less. move it in.
memcpy((unsigned char *)dst + k*size,
(const unsigned char*)bsrc + b++*size, size);
}
}
else
{ // no more b's. move the rest of the a's
// into the target and leave.
memcpy((unsigned char *)dst + k*size,
(const unsigned char*)src + a*size, (alen - a)*size);
k += (alen-a);
}
}
else
{ // else no a's. move the rest of the b's into
// the target and leave.
memcpy((unsigned char *)dst + k*size,
(const unsigned char*)bsrc + b*size, (blen - b)*size);
k += (blen-b);
}
}
// copy final output.
memcpy(src, dst, (alen+blen)*size);
free(dst);
}
最后,此代码不需要任何编译器扩展,例如void*
您在代码中大量利用的违反标准的增量。我强烈建议您远离此类扩展。
以下是用于验证上述算法及其接口的完整测试程序。仔细阅读。
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include <math.h>
#include <time.h>
// simple node definition.
typedef struct node
{
char name[32];
int id;
} node;
// compare two nodes.
int compare_node_names(const void* lhs, const void* rhs)
{
const node* lhn = lhs;
const node* rhn = rhs;
return (strcmp(lhn->name, rhn->name));
}
// compare two nodes.
int compare_node_ids(const void* lhs, const void* rhs)
{
const node* lhn = lhs;
const node* rhn = rhs;
return (lhn->id - rhn->id);
}
// comparator requirements.
typedef int (*fn_cmp)(const void*, const void*);
// merges two lists back to back in a single sequence.
void merge(void *src,
unsigned int alen, // note parition size.
unsigned int blen, // and again here.
unsigned int size,
fn_cmp fcmp)
{
void *bsrc = (unsigned char*)src + alen * size;
void *dst = malloc((alen + blen)*size);
unsigned int a = 0, b = 0, k = 0;
for (k=0; k<(alen+blen); ++k)
{
// still got a's ?
if (a < alen)
{
// still got b's ?
if (b < blen)
{
// get "lesser" of the two.
if (fcmp((const unsigned char*)src + a*size,
(const unsigned char*)bsrc + b*size) <= 0)
{
// a is less. move it in.
memcpy((unsigned char *)dst + k*size,
(const unsigned char*)src + a++*size, size);
}
else
{ // b is less. move it in.
memcpy((unsigned char *)dst + k*size,
(const unsigned char*)bsrc + b++*size, size);
}
}
else
{ // no more b's. move the rest of the a's
// into the target and leave.
memcpy((unsigned char *)dst + k*size,
(const unsigned char*)src + a*size, (alen - a)*size);
k += (alen-a);
}
}
else
{ // else no a's. move the rest of the b's into
// the target and leave.
memcpy((unsigned char *)dst + k*size,
(const unsigned char*)bsrc + b*size, (blen - b)*size);
k += (blen-b);
}
}
// copy final output.
memcpy(src, dst, (alen+blen)*size);
free(dst);
}
// generic mergesort algorithm
void genmsort(void *src, unsigned int len, unsigned int size, fn_cmp fcmp)
{
if (len < 2)
return;
unsigned int mid = len/2;
genmsort(src, mid, size, fcmp);
genmsort((unsigned char*)src+(mid*size), len - mid, size, fcmp);
merge(src, mid, len-mid, size, fcmp);
}
int main()
{
static const unsigned int N = 50;
node *data = malloc(N * sizeof(*data));
int i=0;
srand((unsigned)time(NULL));
for (i=0;i<N;++i)
{
data[i].id = i+1;
sprintf(data[i].name, "String%.3d", 1 + rand() % 999);
}
// sort on names.
genmsort(data, N, sizeof(data[0]), compare_node_names);
for (i=0;i<N;++i)
printf("%s : %u\n", data[i].name, data[i].id);
printf("\n");
// use a different comparator, this time by id.
genmsort(data, N, sizeof(data[0]), compare_node_ids);
for (i=0;i<N;++i)
printf("%s : %u\n", data[i].name, data[i].id);
printf("\n");
free(data);
return 0;
}
输出
String053 : 49
String097 : 38
String104 : 46
String122 : 41
String129 : 8
String139 : 3
String168 : 30
String184 : 22
String222 : 16
String230 : 28
String249 : 4
String265 : 34
String285 : 44
String295 : 20
String298 : 47
String300 : 19
String321 : 2
String375 : 37
String396 : 50
String408 : 13
String430 : 31
String466 : 35
String483 : 24
String484 : 27
String491 : 25
String494 : 39
String507 : 10
String513 : 7
String514 : 11
String539 : 5
String556 : 29
String570 : 43
String583 : 33
String584 : 42
String620 : 15
String632 : 12
String671 : 21
String705 : 23
String710 : 14
String714 : 45
String724 : 18
String733 : 9
String755 : 48
String805 : 36
String814 : 6
String847 : 32
String876 : 40
String893 : 26
String906 : 17
String972 : 1
String972 : 1
String321 : 2
String139 : 3
String249 : 4
String539 : 5
String814 : 6
String513 : 7
String129 : 8
String733 : 9
String507 : 10
String514 : 11
String632 : 12
String408 : 13
String710 : 14
String620 : 15
String222 : 16
String906 : 17
String724 : 18
String300 : 19
String295 : 20
String671 : 21
String184 : 22
String705 : 23
String483 : 24
String491 : 25
String893 : 26
String484 : 27
String230 : 28
String556 : 29
String168 : 30
String430 : 31
String847 : 32
String583 : 33
String265 : 34
String466 : 35
String805 : 36
String375 : 37
String097 : 38
String494 : 39
String876 : 40
String122 : 41
String584 : 42
String570 : 43
String285 : 44
String714 : 45
String104 : 46
String298 : 47
String755 : 48
String053 : 49
String396 : 50