c - 更快地交换结构数组中的元素

Question

我有这个结构:

typedef struct data{
    char name[100], pseudo[100];
    int num0, num1, num2, num3, num4;
    long int lnum0, lnum1, lnum2, lnum3, lnum4;
    double dnum0, dnum1;
}data;
data list[50]

我创建了这个结构的数组，并使用快速排序算法对它们进行排序。 为此，我必须使用此函数交换元素:

void swap(data list[], i, j){
    data tmp;

    tmp.num1 = list[i].num1
    list[i].num1 = list[j].num1
    list[j].num1 =tmp.num1
    //using memmove to avoid overlaping from the strcpy function
    memmove(temp.name,list[i].name,strlen(list[i].name));
    memmove(list[i].name,list[j].name,strlen(list[j].num1));
    memmove(list[j].name,tmp.name,strlen(tmp.name));
}

我的结构中有 16 个元素，我必须重复此函数 16 次才能将它们全部交换。 我的问题是:是否有另一种更简单、更快或更好的方法来进行，或者我们可以优化这个功能吗？

Answer 1

这是对具有 T 类型的 N 个元素的数组进行排序的典型解决方法，其中 N 和 sizeof(T) 被假定为很大。

1. 创建一个由 N 指针组成的临时数组，指向 T。
2. 使用指向实际数组中元素的指针填充临时数组。
3. 对临时数组进行排序。 (比较元素时，必须解引用指针。交换元素时，只需交换单个指针。)
4. 重新排列原始数组中的元素，使其与临时数组中的指针指向的顺序相同。
5. 再次释放临时数组。

此技术的优点是您只需执行 T 的 O(N) 交换，而您可能需要执行 O(N log(N)) 交换 T*。缺点是您必须分配临时缓冲区并在比较元素时经历额外的指针间接寻址。您必须进行基准测试，看看这是否适合您的类型。

一种可能的优化是在堆栈上分配临时数组，因为它永远不会超过排序例程的生命周期。不过，将大型数组放入堆栈可能会导致堆栈溢出，因此请注意大小。