c - 创建一个表示整数数组索引的数组

Question

我们被要求创建一个返回整数指针并接受参数的函数

int *func(int *list,int size)

我想创建一个整数数组，其条目描述了原始数组中的条目在该数组排序时的位置，但不排序原始数组，这应该在函数内部完成然后将指向条目数组的指针返回给主函数。例如:

主数组

3,17,9,2,11,26,5

返回的数组为:

1,5,3,0,4,6,2

我正在考虑将主数组复制到另一个数组后对其进行排序!所以主订单不会丢失，然后将它们比较在一起以填充所需的索引数组，我认为这有点长还有其他想法吗？

Answer 1

您的任务涉及同时对两个数组(值和位置)进行排序。为此，您可以:

• 创建一个辅助数组，在其中重新组织数组以保持值和位置彼此相邻，以便您可以在其上使用qsort；
• 使用(不方便的)非标准 qsort_r，它允许您通过 void * ointer 向排序例程传递额外信息，或者
• 推出您自己的排序算法，使两个数组保持同步。

第一种方法是最常用且可移植的方法。标准排序函数 qsort 可用于数组，其中数组元素可以具有任意大小。因此:创建一个(值，位置)对的辅助数组，按位置对其进行排序并填充结果数组，您必须在堆上分配该数组:

struct pair {
    int val;
    int pos;
};

int paircmp(const void *pa, const void *pb)
{
    const struct pair *a = pa;
    const struct pair *b = pb;

    return (a->val > b->val) - (a->val < b->val);
}

int *func(int array[], int n)
{
    struct pair pair[n];
    int *result;
    int i;

    for (i = 0; i < n; i++) {
        pair[i].val = array[i];
        pair[i].pos = i;
    }

    qsort(pair, n, sizeof(*pair), paircmp);

    result = malloc(n * sizeof(*result));

    for (i = 0; i < n; i++) {
        result[pair[i].pos] = i;
    }

    return result;
}

这里，paircmp是qsort的比较回调函数。

[qsort_r][qsort_r] 方法简洁明了，但 qsort_r 函数是不可移植的 GNU 扩展。还是需要一个辅助阵。 (如果您的数组是排序索引的数组，则甚至不需要这样做。)

步骤与以前相同:创建索引辅助数组，对其进行排序，以便对这些索引处的数组条目进行排序，然后创建结果数组:

int indexcmp(const void *pa, const void *pb, void *data)
{
    const int *a = pa;
    const int *b = pb;
    const int *array = data;

    return (array[*a] > array[*b]) - (array[*a] < array[*b]);
}

int *func2(int array[], int n)
{
    int *result = malloc(n * sizeof(*result));
    int pos[n];
    int i;

    for (i = 0; i < n; i++) pos[i] = i;

    qsort_r(pos, n, sizeof(*pos), indexcmp, array);

    for (i = 0; i < n; i++) result[pos[i]] = i;

    return result;
}

比较函数indexcmp需要一个附加参数。

第三个选项，滚动您自己的排序功能，是最有趣的，但我将把它留给您。