如何快速排序指向 C 中结构的指针数组？

Question

所以有很多使用 qsort() 结构、指针等的例子。但是 none 在我的实现中似乎排序正确。

这是我的代码的概述：

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

struct node {
  int value;
};
typedef struct node Node;

int compare(const void *p1, const void *p2);

int main()
{
    Node *myArray[10];
    Node *node1, *node2, *node3;
    int i;

    node1 = (Node *)malloc(sizeof(Node));
    node1->value = 10;
    myArray[0] = node1;

    node2 = (Node *)malloc(sizeof(Node));
    node2->value = 7;
    myArray[1] = node2;

    node3 = (Node *)malloc(sizeof(Node));
    node3->value = 12;
    myArray[2] = node3;

    for (i=0; i<3; i++) {
        printf("Element %i: %i\n", i, myArray[i]->value);
    }

    printf("-------------\n");

    qsort(myArray, 3, sizeof(Node*), compare);

    for (i=0; i<3; i++) {
        printf("Element %i: %i\n", i, myArray[i]->value);
    }

    return 0;
}

int compare(const void *p1, const void *p2)
{
    Node *node1 = (Node*) p1;
    Node *node2 = (Node*) p2;

    return node1->value - node2->value;
}

这段代码是为了演示我的问题，所以请不要因为语义问题而对我大吼大叫！数组中额外未使用的 space 是故意的。 :p

据我所知，根据我在网上阅读的内容，这应该可行。但事实并非如此。由于某种原因，它开始对比较函数中的垃圾值进行排序。

我要求数组通常大于其中的值，因此希望 qsort() 函数的第二个参数在这种情况下将其限制为仅前 3 个元素。但它似乎忽略了这一点。

知道是什么导致了这种奇怪的行为吗？

Answer 1

当你将*myArray作为第一个参数传递给qsort函数时，就像传递myArray[0]一样，这绝对不是正确的指针（并且会导致未定义的行为 并且很可能是一些奇怪的行为，例如排序 "garbage" 数据）。

要么使用普通 myArray 让数组衰减为指向第一个元素的指针，要么使用 &myArray[0].

显式指定第一个元素

Answer 2

，还有一个。 qsort 将指针传递给 compare 的数组元素，即使它们已经是指针 。所以 compare 得到 Node **，一个双指针。如果你在 compare.

中打印 node->value ，你可以看到这个

据此投射。

static int compare(const void *p1, const void *p2)
{
    const Node *node1 = *(const Node **)p1;
    const Node *node2 = *(const Node **)p2;

    printf("cmp %d %d\n", node1->value, node2->value);
    return node1->value - node2->value;
}

如何快速排序指向 C 中结构的指针数组？

How to quick sort an array of pointers to structures in C?

c

arrays

sorting

quicksort