c - 使用 C 根据对象之间已知的相似性快速对对象数组进行排序

Question

我有一个随机排序的 C 整数数组。

这些数字中的每一个都代表一种颜色，并且与其他地方定义的数组中的每个其他数字都有关系(它们是非线性的，并且基于颜色的亮度和色调)。

我需要一种快速、高效的算法来根据这些数字之间的相似性对它们进行排序。排序要么是使数组中的数字基于相似性进行聚类，要么相反，即彼此相似的数字彼此尽可能远离。

最好的方法是什么？

Answer 1

首先，我假设您将使用 qsort 或类似的函数来进行排序，并且需要一个比较函数来传递给它。这些比较函数的行为类似于 memcnp 和 strcmp —— 返回一个整数来表示小于、等于或大于。

实现此目的的一种方法是将整个颜色值视为一个大数(就比较而言):

int bright_hue_compare(const void * a, const void * b) {
    int rc = bright_compare(a, b);
    if (!rc) {
        rc = hue_compare(a, b);
    }
    return rc;
}

这将首先按颜色的亮度对颜色进行分组(假设您编写了亮度比较函数)，然后按其色调对颜色进行分组。您可能想要交换这些的顺序，并且在内部它们可能会更复杂。

排序使相似的颜色彼此相距更远更为复杂，因为您确实需要一次将其与多个可能的相邻值进行比较，以将它们进一步间隔开。我怀疑您是否可以使用快速排序可靠地获得此结果(stdlib qsort 函数可能不是快速排序，但假设它是):

int bright_hue_inverse_compare(const void * a, const void * b) {
    int rc = bright_hue_compare(a, b);
    if (rc) {
       return 0;
    }
    return random(); // so that they are the same so randomize greater/lesser
}

可能对您来说好足够，但远非最佳结果。

实际上，您可能必须为此编写自己的排序函数，并且它的运行时间可能非常长，因为每种颜色都需要与其许多邻居进行比较。您希望这种分布越优化，这看起来就越像一个人工智能问题，其中每种颜色都希望尽可能远离相似的颜色。

哦，我刚刚想到的可能会产生良好结果的方法是，对所有色调和所有亮度进行平均，然后将数组分成两半，并尝试使每个子数组的平均值与您一样接近可以通过在数组之间交换一些颜色来平衡整个数组的平均值。然后将这些数组分成两半并重复。我不认为你会(并且可能无法)获得最佳结果，但我认为这可能相当不错。找到要交换的内容将是这里最大的问题。