按C中的第二个字段对结构数组进行排序

Question

我的教授建议我们使用 qsort() 对结构数组进行排序。但是，我不得不来发现它并不稳定。我知道还有关于此主题的其他帖子，但 none 似乎提供了一个简单的修复方法来稳定我的排序。有没有一种方法可以将 qsort() 用于第二个数据字段？

这是我的代码：

#include <stdlib.h>
#include <stdio.h>

struct Map * collect_values(int n, int *arr);
void sort_values(struct Map *ptr, int n);
void print(struct Map *print_struct, int n);

struct Map{
    int value, position;
};

int compare(const void *aptr, const void *bptr){
    int a = ((struct Map*)aptr)->value, b = ((struct 
Map*)bptr)->value;
return (a > b) - (a < b);
}

int main(){
    int size, i;
    scanf("%d", &size);
    int *arr = (int*) malloc(size*sizeof(int));
    struct Map *p = collect_values(size,arr);
    qsort(p,size,sizeof(struct Map),compare);
    print(p,size);
    free(p);
    free(arr);
    return 0;
}

struct Map * collect_values(int n, int *arr){
    int i, position = 0;
    struct Map *array = calloc(n,sizeof(*array));
    for(i = 0; i < n; i++){
        scanf("%d",&arr[i]);
        array[i].value = arr[i];
        array[i].position = position;
        position++;
    }
    return array;

}

void print(struct Map * print_struct, int n){
    int i;
    for (i = 0; i < n; i++){
        printf("%d : %d\n", print_struct[i].value, 
print_struct[i].position);
    }
}

现在的输出是：

如何维护重复项的顺序？我花了很多时间试图找出 qsort()，所以如果可能的话我想保留它。

EDIT 我不清楚我想要得到的输出。在排序之前，结构数组包含一个值和该值的索引。所以，原来的结构数组看起来像这样：

排序后，我的代码打印了上面的内容。然而，我所希望的是：

如果第一个字段中的值相等，则需要按第二个字段中的值对它们进行排序，第二个字段永远不会相等，因为它们是索引。

Answer 1

由于该结构有一个 position 成员表示初始数组排序，您可以轻松模拟稳定排序。在比较函数中，如果两个 value 成员相等，则 return 基于 position 成员的排序，如下所示：

int compare(const void *ptr1, const void *ptr2)
{
    const struct Map *aptr = ptr1;
    const struct Map *bptr = ptr2;

    if (aptr->value == bptr->value)
        return (aptr->position > bptr->position) - (aptr->position < bptr->position);
    else
        return (aptr->value > bptr->value) - (aptr->value < bptr->value);
}

按C中的第二个字段对结构数组进行排序

Sorting array of structs by second field in C

c

qsort