c++ - 根据另一个数组的顺序对一个数组进行排序

Question

假设我有一个数组 A[]={8, 9, 11, 14, 16, 20}; 我必须根据另一个数组 B[]={ 6, 5, 1, 2, 4, 3};.

排序的 A 将是 A[]={20, 16, 8, 9, 14, 11};

因此，B 告诉了 A 将如何排序。
B 的第一个元素是最大的，所以 A 的第一个元素也是最大的。 B 的第三个元素是最小的，所以 A 的第三个元素也是最小的

如果 B 像 {100, 84, 74, 51, 5, 1} 这样降序排列，那么 A 也会降序排列。< br/>例子:
1. 如果 B = {12, 8, 14, 156, 2, 84}，A 将是 {11, 9, 14, 20, 8, 16}
2. 如果 B = {2, 3, 45, 0, 7, 56}，A 将是 {9, 11, 16, 8, 14, 20}

就像我有一些不同年龄的 friend ，我想根据他们的年龄给他们一些东西。最年长的人会得到最大的……比他小的人会得到比他小的……等等。

我见过类似的问题，但它们不像我的问题。
我的想法是先对两者进行排序。然后重新排列。

有什么快速解决办法吗？

Answer 1

从您的第一个示例来看，您似乎想要使用索引数组 B 来置换 A。但是第二个示例表明您实际上确实需要排序，但是比较基于 B 中的值而不是 A 中的值。

所以您需要的是一个带有“排序键函数”的排序函数。应该将数组索引作为参数传递给排序键函数。

C 的 qsort 确实有一个键函数，但是键函数的参数是被比较的值，而不是被比较值的索引。所以它对你不起作用。

您可能必须编写自己的排序函数。这并不难。如果数组很小，简单的插入排序就可以了:

void sort_by_keys(int *values, int *sortkeys, int size)
{
   int i, j;

   for (i = 1; i < size; i++) {
     j = i;

     /* For a usual insertion sort, the condition here
      * would be values[j] < values[j-1]. */
     while (j > 0 && sortkeys[j] < sortkeys[j-1]) {
       swap(values, j, j - 1);
       swap(sortkeys, j, j - 1);
       j--;
     }
   }
}

(您必须编写自己的swap。)

如果数组较大，您可以自己编写递归或迭代快速排序代码。这也不难。确保您还编写了一些测试用例以确保它有效。您的测试用例应包括空数组和包含 1 个项目的数组。