Qsort比较函数

Question

我是C的初学者，我试图理解qsort函数所需的比较函数。

第一部分:语法

一个简单的建议用法是这样(我还包括了一些用于打印结果的main()代码)：

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

int values[] = { 40, 10, 100, 90, 20, 25, 12, 13, 10, 40 };

int compare(const void *a, const void *b)
{
    const int *ia = (const int *)a; // casting pointer types 
    const int *ib = (const int *)b;
    return *ia  - *ib; 
}

int main()
{
    int n;
    for (n=0; n<10; n++)
    {
        printf("%d ",values[n]);
    }
    printf("\n");
    qsort(values, 10, sizeof(int), compare);
    for (n=0; n<10; n++)
    {
        printf("%d ",values[n]);
    }
    printf("\n");
    system("pause");
    return 0;
}

我不明白为什么需要比较函数中的所有额外内容，因此我将其简化为：

int compare (int *a, int *b)
    {
        return *a-*b; 
    }

这仍然有效，并产生相同的结果。有人能向我解释一下我移走了什么吗?为什么它仍然有效？

第二部分:为什么是指针？

另外，我真的需要使用指针吗？为什么我不能像这样直接比较"a“和"b”(这不起作用)：

int compare (int a, int b)
        {
            return a-b; 
        }

由于某些原因，使用多维数组，我能够逃脱不使用指针的影响，而且由于某种原因，它起了作用！怎么一回事？(按每个子数组中的第二项排序多维数组的示例代码)：

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

int values[7][3] = { {40,55}, {10,52}, {100,8}, {90,90}, {20,91}, {25,24} };

int compare(int a[2], int b[2])
{
    return a[1] - b[1];
}

int main()
{
    int n;
    for (n=0; n<6; n++)
    {
        printf("%d,",values[n][0]);
        printf("%d ",values[n][1]);
    }
    printf("\n");
    qsort(values, 6, sizeof(int)*3, compare);
    for (n=0; n<6; n++)
    {
        printf("%d,",values[n][0]);
        printf("%d ",values[n][1]);
    }
    printf("\n");
    system("pause");
    return 0;
}

我真的很高兴多维数组排序正在工作，因为这是我的最终目标，但我不知道我是如何使它工作的(除了运气不好和代码被砍碎之外)，所以我很想解释一下为什么我提供的一些示例工作，为什么有些不工作！

Answer 1

这仍然有效，并产生相同的结果。有人能向我解释一下我移走了什么吗?为什么它仍然有效？

您正在调用C中未定义的行为，参见C99 6.3.2.3指针/8：

指向一种类型的函数的指针可以转换为指向另一种类型的函数的指针，然后再转换回来；结果应该与原始指针相比较。如果转换后的指针用于调用类型与指向类型不兼容的函数，则该行为是未定义的。

在C++中，这个程序是完全错误的：http://ideone.com/9zRYSj。

它仍然“碰巧”工作，因为compare函数需要一对指针；在您的特定平台上，sizeof(void*)与sizeof(int*)相同，因此调用int(void *, void *)类型的函数指针(实际上包含指向int(int *, int *)类型函数的指针)实际上与在特定时间点对特定平台上的指针类型转换相同。

另外，我真的需要使用指针吗？为什么我不能像这样直接比较"a“和"b”(这不起作用)：

因为qsort对任何两种类型都有一个通用的比较函数，而不仅仅是int。因此，它不知道指针被取消引用的类型。

由于某些原因，使用多维数组，我能够逃脱不使用指针的影响，而且由于某种原因，它起了作用！怎么回事！

这是因为以下原型是相同的：

1. int foo(int *a, int *b);
2. int foo(int a[], int b[])

也就是说，数组在传递给函数时会衰减为指针。如您所做的那样，显式地指定数组的长度：

int foo(int a[2], int b[2])

使编译器使sizeof和其他编译时间位将项作为两个元素数组来处理；但是函数在到达机器级别时仍然接受一对指针。

在任何情况下，传递不接受一对void *的比较函数都会导致未定义的行为。“未定义行为”的一个有效结果是“它似乎只是起作用了”。另一个有效的结果将是“它在星期二工作”或“它格式化硬盘”。不要依赖这种行为。

Answer 2

我不明白为什么你需要比较函数中的所有额外的东西，所以我把它简化为

是否使用const限定符取决于您。您应该不会修改比较器中的值。但是，可以抛弃const，违背您对编译器的承诺。

Q排序需要一个函数指针，它以两个const void *作为参数，这就是为什么为比较器函数传递指针的原因：

   void qsort(void *base, size_t nmemb, size_t size,
                  int(*compare)(const void *, const void *));

因此，传递a和b将导致将值解释为指针，这显然是错误的。

它在不传递多维数组指针的情况下工作，因为当您传递数组时，它们会衰减为指针。所以下面的比较器是可以的。

int compare (int a[2], int b[2])
{
    return a[1] - b[1];
}

Answer 3

答案非常简单:从qsort http://pubs.opengroup.org/onlinepubs/009695399/functions/qsort.html的手册中，函数指针的原型是：

int comp(const void *a, const void *b)

与此原型相关联的ty胡枝子可以这样声明。

typedef int (*comp_qsort_funct_t) ( const void *, const void * )

其中comp_qsort_funct_t是函数指针的类型。

qsort的比较函数的原型使用const变量，因为这是一个很好的实践/设计，因为数据不会被修改。

使用不同的原型可能会导致意外的结果，这取决于编译器/平台。或者编译失败，如注释：http://ideone.com/9zRYSj中提供的示例

所以你不能使用不同的原型。