c - C中的菱形数组排序

Question

我在 C 语言中有以下家庭作业。我基本上需要一种方法而不是解决方案。

我们有一个 13 x 13 的数组。在数组中，我们有一个需要考虑的菱形。此菱形之外的所有内容都初始化为 -1（不重要）。下面的示例 5 x 5 数组 -

x x 1 x x 
x 2 2 2 x
3 3 3 3 3
x 4 4 4 x
x x 5 x x

x=-1

现在在这个数组中，我们在菱形中为每​​个条目拥有的值包含 11 位。5 lsb 包含一个数据（色调），其他 6 个包含另一个数据（直径）。我们需要按行对数据进行排序，单调地对色调进行排序，然后按列对直径进行单调排序。

这样做的最有效和最节省内存的方法是什么？由于我们需要保存这一点，因此最好交换条目而不是创建另一个数组。最后，我们将得到一个排序好的菱形数组（仍然是 -1）。非常感谢你们！

Answer 1

我不明白您到底想如何重新排序元素

逐行，单调地表示色调，然后逐列表示直径，单调地

但这里有一些你可以使用的想法。

• 您的数组是 13x13（169 个元素）；除此之外，几乎正好有一半 (84) 是空的，因此您可以将它们用作临时存储（例如radix-sort）。
• 您的值有 11 个有意义的位；真实计算机中的数字有 16 位或 32 位 - 因此您可以使用 5 个（或 21 个，取决于您的系统）最高有效位作为临时存储。
• 使用高 5 位的一种可能的好方法是将 5 LSB（色调）的副本放在那里。这将在进行正常整数比较时反转两个部分的重要性（使色调比直径更重要）

Answer 2

我懂了。
我想这样的菱形可以直接用数组来表示。
忽略所有-1条目。

{ row-0 row-1 row-2 row-3 ... row-13 }

{ 1 2 2 2 3 3 3 3 3 4 4 4 5 }

您现在可以根据需要对数组进行排序。
排序两次，一次是色相，一次是直径；或弄清楚如何按两个标准对数组进行排序。

如果您只是编写一个将数组索引转换为菱形坐标的函数，您也可以就地工作。完成后，您可以像处理数组一样处理菱形结构。

Answer 3

用这个原型编写一个排序例程：

void sort(int startx, int starty, int dx, int dy, int count, int (*compare)(int, int));

或者

void sort(int *start, int stride, int count, int (*compare)(int,int));

编写几个比较函数，并在两个 for 循环中调用 sort，一个用于行，另一个用于列。