c - 找出 C 中 k 个最小值的索引

Question

我正在用 C 实现 K 最近邻算法，我已经计算了大小为 m 的待标记集合中每个点到已标记集合中每个点的距离矩阵大小为 n 的集合。这个矩阵的格式是

[[dist_0,0 ... dist_0,n-1]
 .
 .
 . 
 [dist_m-1,0 ... dist_m-1,n-1]]

接下来，我需要找到每行中的 k 个最小距离，以便我可以使用列索引访问这些点的标签，然后计算行索引所指的点的标签。后一部分是微不足道的，但计算 k 最小距离的索引让我感到难过。 Python 有简单的方法来做这样的事情，但 C 的基本性质让我有点沮丧。我会很感激一些关于该做什么的指示(没有双关语意)以及 C 可能需要帮助的任何有用的功能。

Answer 1

在不知道 k 的情况下，假设它是可变的，最简单的方法是:

1. 在包含原始列索引的结构中组织每个元素。
2. 按升序对矩阵的每一行进行排序，并取该行的前 k 个元素。

---

struct item {
    unsigned value;
    size_t index;
};

int compare_items(void *a, void *b) {
    struct item *item_a = a;
    struct item *item_b = b;

    if (item_a->value < item_b->value)
        return -1;
    if (item_a->value > item_b->value)
        return 1;
    return 0;
}

// Your matrix:
struct item matrix[N][M];

/* Populate the matrix... make sure that each index is set,
 * e.g. matrix[0][0] has index = 0.
 */

size_t i, j;

for (i = 0; i < M; i++) {
    qsort(matrix[i], N, sizeof(struct item), compare_items);

    /* Now the i-th row is sorted and you can take a look
     * at the first k elements of the row.
     */
    for (j = 0; j < k; j++) {
        // Do something with matrix[i][j].index ...
    }
}