3

通常对结构对象数组进行排序很容易。考虑结构数组 (AOS)

#define ITEMS 10

typedef struct MyStruct
{
 char a;
 int  b;
}tMyStruct;

tMyStruct arr_mystruct[ITEMS];

我首先用 < a , b> 对的值填充这个结构数组。

如果我现在想根据整数字段对这个结构数组进行排序，我可以使用 libc qsort 函数通过使用带有两个整数参数的比较函数来完成。

现在考虑我用 SOA 格式替换上面的 AOS 格式的结构

#define ITEMS 10

typedef struct MyStruct
{
 char a[ITEMS];
 int  b[ITEMS];
}tMyStruct;

tMyStruct mystruct;

现在我仍然可以使用 qsort 对整数数组 b 字段进行排序，但是这次我需要另外对 a（字符数组）wrt b 的排序顺序进行排序。

所以我的问题是，对以 SOA 格式而不是通常的 AOS 格式布局的数据进行排序的一种可能有效的方法是什么？

谁能帮我这个 ？谢谢！

4

2 回答 2

0

可能最好的方法是使用辅助数组：

int helper[ITEMS];

int helper_cmp(const void *a, const void *b);

for (i = 0; i < ITEMS; ++i)
    helper[i] = i;
qsort(helper, ITEMS, sizeof(*helper), helper_cmp);

该helper_cmp函数将helper值作为索引mystruct.b并比较这些值：

int helper_cmp(const void *a, const void *b)
{
    int first = *(const int *)a;
    int second = *(const int *)b;
    int b_first = mystruct.b[first];
    int b_second = mystruct.b[second];
    // compare b_first and b_second
}

然后，在 之后qsort，辅助数组将包含重新排列的索引b，告诉它应该如何排序。

您可以使用此数组重新排列mystruct.a和mystruct.b.

请注意，这不如排序“结构数组”有效。我不知道你的应用程序，但我的猜测是“数组结构”，其中数组的字段是相关的，首先不是一个好主意。也就是说，如果排序b影响 排序a，它们可能属于同一个概念元素（如果需要，可以将其称为类），最好将它们组合在一起struct。

于 2012-07-27T15:34:49.937 回答
0

除了辅助建议之外，没有办法使用 qsort() 来执行此操作。对于这样的情况，我会编写自己的排序函数。为了在速度和易于编写之间取得最佳平衡，我发现插入排序适用于小型数组，而合并排序适用于大型数组。

于 2012-08-01T00:13:43.003 回答