排序时保持两个数组的顺序相同

Question

我有一个需要排序的包含 unix 时间的整数数组。我打算使用 qsort 对其进行排序，这很简单。但是，我还有一个 "strings" 数组，需要保持与整数数组相同的顺序。

因此整数数组中的位置 2 将对应于另一个数组中位置二的元素。

有没有用qsort维持这样的关系？

Answer 1

这样做

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

struct Data
{
    long int time;
    const char *string;
};

int
datacmp(const void *const x, const void *const y)
{
    return ((struct Data *) x)->time - ((struct Data *) y)->time;
}

int
main(void)
{
    struct Data array[] = {
        {1234, "1234 Text"},
        {1034, "1034 Text"},
        {1041, "1041 Text"}
    };
    size_t count;

    count = sizeof(array) / sizeof(array[0]);
    for (size_t i = 0 ; i < count ; ++i)
    {
        fprintf(stderr, "Entry %zu:\n\ttime  : %ld\n\tstring: %s\n\n", 
            i, array[i].time, array[i].string);
    }

    fprintf(stderr, "\n");
    qsort(array, count, sizeof(array[0]), datacmp);
    fprintf(stderr, "---- Sorted array:\n");

    for (size_t i = 0 ; i < count ; ++i)
    {
        fprintf(stderr, "Entry %zu:\n\ttime  : %ld\n\tstring: %s\n\n", 
            i, array[i].time, array[i].string);
    }

    return 0;
}

Answer 2

一个更通用的解决方案，实际上根据其中一个数组对 2 个（或更多）数组进行排序，方法是对指向键数组的指针数组进行排序，然后重新排序所有数组以对它们进行排序（它还恢复指针数组回到它们的初始状态）。比较函数只需要知道指针指向的类型。就地重新排序需要 O(n)（线性）时间，因为每次移动都会在其最终排序位置放置一个值。在此示例中，a[] 是一个整数数组，b[] 是一个指向字符串 (char *) 的指针数组。

int compare(const void *pp0, const void *pp1)
{
    int i0 = **(int **)pp0;
    int i1 = **(int **)pp1;
    if(i0 > i1)return -1;
    if(i0 < i1)return  1;
    return 0;
}
/* ... */

    int *pa = malloc(...);   /* array of pointers */
    int ta;    /* temp value for a */
    char *tb;  /* temp value for b */
    /* ... */

    /* initialize array of pointers to a[] */
    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++)
        pa[i] = &a[i];
    /* sort array of pointers */
    qsort(pa, sizeof(a)/sizeof(a[0]), sizeof(pa[0]), compare);
    /* reorder a[] and b[] according to the array of pointers */
    for(i = 0; i < sizeof(a)/sizeof(a[0]); i++){
        if(i != pa[i]-a){
            ta = a[i];
            tb = b[i];
            k = i;
            while(i != (j = pa[k]-a)){
                a[k] = a[j];
                b[k] = b[j];
                pa[k] = &a[k];
                k = j;
            }
            a[k] = ta;
            b[k] = tb;
            pa[k] = &a[k];
        }
    }

排序时保持两个数组的顺序相同

Keeping two arrays in the same ordering when sorting

c

arrays

sorting

qsort