0

我有一个连续的内存块，其中前 N 个字节都包含 A 类型的对象，其余字节包含 B 类型的元素。例如，我可能有 120 个 A 类型的对象，然后是 40 个 B 类型的对象。

A 型和 B 型都是大小不同的结构，但都有一个整数成员“索引”，这是我想要排序的。基本上我想得到一个按索引排序的数组，我目前有一个按数据类型排序的数组。理想情况下，我希望最终按索引排序，然后按类型排序，所以类似于

Index==1 elements | Index==2 elements | ... | Index==L elements
Type A   | Type B | Type A  |  Type B | ... | Type A| Type B

到目前为止，我想出的唯一方法是按索引分别对 A 型和 B 型块进行排序，然后使用 memcopy 将它们打乱，使它们看起来像上面那样。有更好的解决方案吗？

4

3 回答 3

2

原始数组是如何设置的？在同一个数组中混合不同类型似乎是个坏主意。是否有理由需要将它们放在同一个数组中？

如果它们必须在同一个数组中，您可能需要使用联合。就像是

enum myType { A, B };
struct typeA { myType type; int key; ... data ... }
struct typeB { myType type; int key; ... data ... }
union myTypes { typeA myA; typeB myB }
myTypes data[128];

您现在可以使用 C 库中的qsort函数。

另一种选择是使用一个单独的指向对象的指针数组，然后对该辅助数组进行排序。不过，您仍然需要在每个结构的开头使用某种类型字段。

于 2013-09-17T08:48:37.857 回答
1

而不是建议的指针，您可能希望使用由类型和指针组成的结构（后者甚至作为两个不同指针的联合）。在这种情况下，您可以轻松区分对象的类型 - 除非它们在同一位置具有 ID 字段。

所以假设你有

struct typeA {
    int whatever;
    int id;
}

struct typeB {
    double whatever;
    int id;
}

你被咬了，必须按照我说的做：

struct typptr {
    enum type { typ_A, typ_B } type;
    union {
        struct typeA * Aptr;
        struct typeB * Bptr;
    }
}

int getID(struct typptr t)
{
    if (t.type == typ_A) {
        return (t.Aptr)->id * 2;
    } else {
        return (t.Bptr)->id * 2 + 1; // have B always sorted after A...
    }
}

这样，您可以轻松地为 qsort 编写 cmp 函数以对struct typptrs 进行排序。

如果类型是“形状相似”，例如

struct typeA {
    int id;
    int whatever;
}

struct typeB {
    int id;
    double whatever;
}

即id一开始就有字段，事情更容易（但我不知道这是否可移植），因为您总是可以投射到其中一个并读出id字段。所以你只需要一个指针数组并且可以省略类型字段。

于 2013-09-17T09:10:40.377 回答
0

您稍后的评论中有重要信息 - 类型最初并未混合。如果是这样，您可以单独对每个数组部分运行一个排序阶段（快速排序或您想要的任何其他方法），然后在两个数组之间进行最后一个合并排序阶段（假设您可以节省额外的空间）

那仍然是 NlogN + N = NlogN

于 2013-09-17T09:13:28.513 回答