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

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

这些数字中的每个数字都代表一种颜色，并且与其他位置定义的数组中的其他每个数字都有关系（它们是非线性的，并且基于颜色的亮度和色相）。

我需要一种快速，高效的算法，根据彼此之间的相似性对这些数字进行排序。排序既可以使数组簇中的数字基于相似度，也可以相反，即以彼此相似的数字尽可能远的方式。

最好的方法是什么？

最佳答案

首先，我假设您将使用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;
}

这将首先根据颜色的亮度（假设您编写了亮度比较功能）对颜色进行分组，然后根据其色相对颜色进行分组。您可能需要交换这些命令的顺序，在内部它们可能会更复杂。

排序以使相似的颜色彼此之间的距离更加复杂，因为您确实需要一次将其与多个值（可能相邻的值）进行比较以将它们进一步隔开。我怀疑您是否可以通过quicksort可靠地获得它（stdlib qsort函数可能不是quicksort，但假设是），但是：

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
}

可能对您来说已经足够好了，但收益远非最佳结果。

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

哦，我刚才想到的可能会产生好的结果是，如果将所有色调和所有亮度取平均值，然后将阵列分成两半，并尝试使每个子阵列的平均值尽可能接近您可以通过在阵列之间交换一些颜色来平衡整个阵列的平均数。然后将这些数组一分为二并重复。我认为您不会（也可能无法）获得最佳效果，但是我认为这可能会很好。找到要交换的东西将是这里最大的问题。