使用qsort（）对整数数组进行排序并交换字符串

Question

我希望能够将一个 int *arr 按降序排序，并在同一时间内，如果 int *arr 的第二个元素大于第一个元素，则交换相应的 char **words 数组元素。我该如何使用 qsort() 和 cmpfunc() 来实现这一点？排序 ints 很容易，但是如何交换另一个数组中的字符串，因为我没有索引知道 int 数组中哪两个元素目前已排序？

qsort(arr,N,sizeof(int),cmpfunc);

``

int cmpfunc(const void * a, const void * b) {
    int val1 = *(int *)a;
    int val2 = *(int *)b;

    if(val2 > val1) {
        /* swap string positions */
        return 1;
    } else if(val2 < val1) {
        return -1;
    } else {
        return 0;
    }
}

- Stelios Papamichail

---

你需要创建另一个数据结构来“链接”这两个数组，并编写比较函数。 - Eugene Sh.

为什么要将它们放在两个不同的数组中？为什么不创建一个由结构体组成的数组，其中结构体包含整数和字符串？ - Barmar

如果arr在cmpfunc中可用（例如，因为它是文件作用域的变量），那么您可以推导出索引；但这当然是一种hack方法。 - Stephan Lechner

@Barmar 那么就像这样：struct obj { int count; char *word; };，然后创建一个由N个这样的结构体组成的数组，并将该数组作为基础传递给qsort？ - Stelios Papamichail

@SteliosPapamichail 是的。您还需要使用此类型运行相应比较函数。 - Eugene Sh.

Answer 1

有几种方法可以解决这个问题。首先，直接回答你的问题：

1. 创建一个包含值0..N的size_t类型新数组。
2. 在该数组上运行qsort函数，其中

int val1 = *(int *)a;
int val2 = *(int *)b;

你需要做什么

int val1 = arr[*(int *)a];
int val2 = arr[*(int *)b];

然后像往常一样进行比较。

3. 现在你有一个 arr 的索引数组（一种排列），按照这个顺序可以使 arr 排序。现在我们可以将这个排列应用到 arr 和 words 上。一种选择是每当你想要按排序顺序访问这两个数组时，只需循环遍历索引数组。另一种选择是复制这两个数组，然后根据排列复制元素。

其次：您也可以使用一个指向 arr 的成员和相应的 words 成员的结构体数组 struct { int * ; char ** } 来执行同样的操作，在保持原始数组不变的情况下按其 int 成员对该数组进行排序，并从那里使用它们。

第三：你可以先避免使用并行数组。如果数据如此密切相关，为什么要放在两个无关的变量中呢？如果你一开始就把这两种数据放在一个结构体中，那么你就可以对结构体数组进行排序，并且不必担心相关性会失步。

- hobbs

---

你是对的，我觉得我应该重构我的代码并实现你刚提到的第三种方式。我仍然有一个问题，就是那些结构体的比较函数是否应该像这样：int cmpfun(const void *a,const void *b) { struct obj a = *(struct obj b *) a; // 对于b也是一样，然后我可以使用.运算符访问每个结构体的字段吗？ } - Stelios Papamichail

我刚刚实现了你刚提到的第三种方法，但是字符串交换没有按照预期工作。你介意和我一起看看代码中的那部分吗？ - Stelios Papamichail

Answer 2

你可以使用qsort_r()（如果可用，它是GNU扩展。在Microsoft环境中被称为qsort_s()，但语义相同）向比较函数传递另一个参数，例如基本数组指针int *arr和char **words在结构体中：

struct cmpargs {
    int *arr;
    char **words;
} args;

...

args.arr = arr;
args.words = words;

qsort_r(arr,N,sizeof(int),cmpfunc, &args);

在您的比较函数中，您现在可以访问这些内容并使用它们进行交换：

int cmpfunc(const void * a, const void * b, void *_args) {
    struct cmpargs args = _args;

    int *a1 = a;
    int *a2 = b;

    int idx1 = a - args->arr;
    int idx2 = b - args->arr;

现在，如果您的比较函数返回1，则可以交换对应数组args->word中的元素。

- Ctx

Answer 3

我想要按降序排序一个int *arr数组，并且同时，如果第二个元素大于第一个元素，则交换char **words数组的相应元素。如何使用qsort()和cmpfunc()实现这一点？

按照所述方式进行操作并不容易，因为它需要上下文信息，而qsort()无法将其传递给比较函数：即arr和words数组的基地址。事实上，后者甚至在首次调用qsort()时也没有被传递给它。

在支持C11线程的实现中，一种可行的替代方案是将这些指针存储在线程特定存储中，并让比较函数从那里检索它们。然后，您可以通过它们之间的指针差异和基本指针计算要比较的元素的索引，并使用其基本指针和所获得的索引执行words的正常交换。

但这可能不是您真正想要的！我推断您正在尝试获得与arr元素相同的元素排列顺序。您所描述的方式并不能保证产生这种结果，因为您无法确定qsort()每次比较结果按某种方式进行交换。

如果确实需要这两个数组分开，正确的方法是准备并排序某种辅助数组。在这个领域有几种选择，可以让您重新排序一个或两个主数组，或者像已经完成的那样访问它们。例如，您可以准备一个int (*perm)[2]，每个元素（一个int[2]）包含arr的相应元素及其初始索引。然后，您可以按照所需的方式对这个数组进行排序，并直接得到排列。然后，您可以重新排序arr和words以匹配，或通过排列间接访问它们（words[perm[k][1]]）。

但是，您也可以考虑编写自己的专用排序函数，而不是使用qsort()。这样的函数可以将两个数组的基本指针作为参数--甚至是正确类型的--然后直接执行您需要的协同排序。

- John Bollinger