使用qsort对多个数组进行排序

Question

我有一个结构体，其中包含多个数组。我需要能够对这些数组中的任何一个进行排序，并根据排序后的数组移动其他数组中的元素。

struct arrayset
{
int values1[] = { 32, 10, 101, 72, 13, 5 };
int values2[] = { 40, 10, 100, 90, 20, 2 };
int values3[] = { 16, 14, 93, 2, 37, 39 };
};

我知道如何处理其中一个数组，但我不确定有什么优雅的方法可以更改另外两个数组中的元素。我不想对另外两个数组进行排序，而是希望在排序后它们的元素能够继续匹配，而不会混淆。有什么建议吗？

qsort(arrayset.values1,6,sizeof(int), compare);
//values2/3 elements would follow values1's elements

- user3287789

---

有没有可能有 struct set { int v1, v2, v3; } array[6];？ - cnicutar

不确定您的意思，请详细说明一下？您是在指出结构上的问题，还是想知道我能否以不同的方式声明数组？ - user3287789

看起来你想把三个值分组在一起。你可以用这三个值创建一个结构体，然后再创建一个包含这些结构体的数组。接着，你可以使用自定义比较函数（按element.v1进行比较）对该数组进行快速排序(qsort)。最终你将得到按v1排序的元素，并能够获取与v1元素相应的v2和v3。 - cnicutar

在结构体的定义中，不能分配其成员。这仅在 C++11 中有效。 - ajay

Answer 1

在需要对多个独立数据结构进行同步重排的情况下，您可以遵循以下两种方法之一：

1. 内部侵入式方法 - 即提供自己的交换函数，以同步地交换三个数组中的元素。 2. 外部非侵入式方法 - 将排序过程分解为两个独立的步骤：首先从“主”数组生成排序置换，然后将该排序置换独立地应用于三个数组中的每一个。

第一种方法可能更容易实现，但它有一些明显的缺点。随着数据集数量和/或元素本身变得更重，交换函数也会变得更重。对于基于物理复制元素的排序算法来说，这不是一件好事，因为这样的算法可能会多次重新定位（交换）每个元素。

第二种方法本质上是基于间接的索引排序，这意味着它对元素复制的重量不太敏感。第二种方法只在知道其最终位置时才一次复制每个实际元素。

要生成排序置换，您只需要使用初始化为 {0, 1, 2, 3, ...} 的整数索引数组 p。而不是直接对 values1 进行排序，对此索引数组 p 进行排序，使其产生适合 values1 数组的正确顺序。 （标准的 qsort 函数对这种应用程序的效果不是很好，因为它是无上下文的。）

排序后，该索引数组将作为您的置换。您只需要根据该置换重新排列您的三个数组中的每一个。它可以在原地完成或者更容易地在外部完成，具体取决于您的需求。

在您的特定示例中，您将从索引数组开始。

p = { 0, 1, 2, 3, 4, 5 }

排序后，它将变为：

p = { 5, 1, 4, 0, 3, 2 }

这是一个针对你的values1数组的所谓的来自排列：它告诉你为了获得values1的排序版本，位置i上的元素应该来自values1[p[i]]。现在，你需要做的就是使用相同的来自排列p生成重新排列的values1、values2和values3版本。

同样，后一步很容易在原位完成，但更难以原地完成。在这里，你可以找到一些相关的来自排列原位重新排列的实现：In-place array reordering?

- AnT stands with Russia

---

@user3287789：如果元素数量少于十个，冒泡排序还可以。否则，随着元素数量的增加，冒泡排序的时间呈指数级增长，不再适用。 - wallyk

@user3287789：我不确定冒泡排序与问题有什么具体关系。您可以使用任何排序算法来实现任一方法。冒泡排序是否好或不好是完全不同的故事。 - AnT stands with Russia

Answer 2

每当我遇到这种问题时，我会获取一个qsort实现，并修改它以接受除比较函数外的附加交换函数。

通过这种方式，您可以在所有并行数据中交换项目。

- wallyk

Answer 3

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

struct arrayset {
    int *values1;
    int *values2;
    int *values3;
};

void custom_sort(struct arrayset *v, size_t size);

int main() {
    struct arrayset work = {
        (int []){ 32, 10, 101, 72, 13, 5 },
        (int []){ 40, 10, 100, 90, 20, 2 },
        (int []){ 16, 14,  93,  2, 37, 39}
    };
    custom_sort(&work, 6);
    for(int i=0;i<6;++i){
        printf("%d, %d, %d\n",
            work.values1[i], work.values2[i], work.values3[i]);
    }
    return 0;
}

typedef struct pair {
    int key, value;
} Pair;

int cmp(const void *x, const void *y){
    int a = ((const Pair*)x)->key;
    int b = ((const Pair*)y)->key;
    return a < b ? -1 : a > b;
}

void custom_sort(struct arrayset *v, size_t size){
    Pair key[size];
    for(int i=0;i<size;++i){
        key[i].key  = v->values1[i];
        key[i].value=i;
    }
    qsort(key, size, sizeof(Pair), cmp);
    int v1[size], v2[size], v3[size];
    memcpy(v1, v->values1, size*sizeof(int));
    memcpy(v2, v->values2, size*sizeof(int));
    memcpy(v3, v->values3, size*sizeof(int));
    for(int i=0;i<size;++i){
        v->values1[i] = v1[key[i].value];
        v->values2[i] = v2[key[i].value];
        v->values3[i] = v3[key[i].value];
    }
}

- BLUEPIXY