使用qsort同时对两个数组进行排序？

Question

我可以对指向单词的指针数组进行字母顺序排序，但问题在于我还需要将整数数组（特定单词使用次数的数量）排序，以使整数与它们相应的单词在同一位置：

我的代码：

for (i = 0; i < numWords; i++) {
    // prints out the words and their frequency respectively
    printf("%s - %d\n", dictionary[i], frequency[i]); 
}

//sorts the dictionary so that the words are 'alphabetical'
qsort(dictionary, numWords, sizeof(char *), rstrcmp);  
printf("\nafter qsort\n");  //checkmark

for (i = 0; i < numWords; i++) {
    // prints the word list alphabetically, but the frequencies are no longer matched
    printf("%s - %d\n", dictionary[i], frequency[i]); 
}

...比较函数 V

int rstrcmp(const void *p1, const void *p2) {
    return strcmp(*(char * const *)p1, *(char * const *)p2);
}

- nobodyImportant

---

理想情况下，您可以使用哈希表/映射，其中单词是键，频率是值，并根据键排序。 - bwegs

一个简单的方法是使用结构体来存储单词/频率对，然后对这些结构体的数组进行排序。 - Turix

@Turix，我可能有点困难，我不擅长指针和何时使用它们；我勉强能应付，能否给个例子来初始化结构体数组？ - nobodyImportant

@nobodyImportant 好的，我在下面的答案中添加了一些示例代码。 - Turix

Answer 1

一个简单的做法是使用结构体来存储单词/频率对，然后对这些结构体的数组进行排序。

例如：

struct WordFrequency
{
    const char * word;
    int frequency;
} wordFreqs[numWords];        // Assumes numWords is static/global and constant...

然后：

for (i = 0; i < numWords; i++) {
    printf("%s - %d\n", dictionary[i], frequency[i]);
    wordFreqs[i].word = dictionary[i];
    wordFreqs[i].frequency = frequency[i];
}

//sorts the dictionary so that the words are 'alphabetical'
qsort(wordFreqs, numWords, sizeof(struct WordFrequency), wfcmp);  

for (i = 0; i < numWords; i++) {
    printf("%s - %d\n", wordFreqs[i].word, wordFreqs[i].frequency); 
}

同时：

int wfcmp(const void *p1, const void *p2) {
     return strcmp(((const struct WordFrequency *)p1)->word, ((const struct WordFrequency *)p2)->word);
}

- Turix

Answer 2

标准的qsort()函数不能直接满足您的需求。撇开其他不谈，它如何知道（或者您如何告诉它）要并行排序哪两个数组呢？

您可以改变数据结构（使用结构类型的数组），或者编写自己的排序函数。两者中，改变数据结构可能更容易。

还有另一种选择——但是有些复杂。您可以创建一个int数组，使其具有以下特点：

for (int i = 0; i < N; i++)
    index[i] = i;

您可以将这个数组和一个比较器一起传递给排序函数，比较器知道两个数组的基地址。 qsort() 函数会对数组中的数据进行置换；比较器查看其他数组中的数据。另外两个数组必须是全局变量（至少是文件范围），或者您需要全局变量指针，可以用这两个数组的基地址初始化。

排序后，您可以使用 array1[index[i]] 和 array2[index[i]] 访问已排序数组的第 i 个元素。

如果您在BSD上，还有另一种选择：可以使用 qsort_r() 函数。

 void qsort_r(void *base, size_t nel, size_t width, void *thunk,
              int (*compar)(void *, const void *, const void *));

'thunk'是指针，作为第一个参数传递给比较器。您可以将其与索引数组方案一起使用，将两个数组的指针传递到比较器中，因此您根本不需要文件范围变量。但是，您仍然无法进行两个独立的交换，因此必须使用索引数组方案。

- Jonathan Leffler

---

对于GNU系统，还有一个不同原型的void qsort_r(void *, size_t, size_t, int (*)(const void *, const void *, void *), void *arg);。 - mafso

@mafso：有趣。一致性——谁需要一致性？ - Jonathan Leffler

FYI（我不得不查一下）：GNU版本的设计是为了只需要实现一个函数（参见glibc邮件列表），因为...，嗯，因为某些版权原因（？）。哦，为了完整起见，Microsoft的CRT和C11 Annex K指定了qsort_s，前者将上下文指针作为比较函数的第一个参数，后者将其作为最后一个参数。你说得对，没有人需要一致性！ - mafso

@mafso：研究得很好。我已经在记录中表明对于TR 24731-1（现在是Annex K）并不热衷。你是对的。qsort_s()的Microsoft规范遵循了qsort_r()的BSD变体。"标准"版本遵循了GNU变体的qsort_r()。这只是另一个理由，要对C扩展中定义不一致的函数保持谨慎。 - Jonathan Leffler

感谢指点！仅供参考：MS和BSD版本采用相同类型的比较函数，但与您的示例不兼容（与thunk和compar相比，需要在MS中进行切换），而GNU和Annex K似乎是兼容的。 - mafso

Answer 3

一个有用的排序并行数组的方法：创建一个整数数组（严格来说是size_t），并用值0到numWords-1初始化它。然后使用一个比较函数对该数组进行qsort排序，该比较函数执行strcmp(dictionary[*(int *)p1], dictionary[*(int *)p2])，然后使用排序后的索引数组同时对dictionary和frequency进行排列（这可以通过复制非常容易地完成，或者通过交换在原地以稍微困难一些的方式实现: 此处提供了后者的示例）。

不过，使用结构体数组可能是更好的解决方案，这样就避免了整个问题。

- hobbs

---

+1 对于原地交换算法的交叉引用。 - Jonathan Leffler

@hobbs，你能展示一下在qsort中使用的函数定义，以访问本地字符串数组吗？ - Vlad from Moscow