使用 qsort() 函数

Question

我是一名学生&我在一本书上查到了这个函数。它按其应有的方式工作，但我不太了解传递给 qsort() 函数的 sortFunction() 的内部工作原理。如果有人可以详细解释一下，请这样做。提前致谢。

#include<iostream>
#include<stdlib.h>

using namespace std;

//form of sort function required by qsort()
int sortFunction(const void *intOne,const void *intTwo);

const int tableSize = 10;

int main()
{
    int i, table[tableSize];

    //fill the table with values
    for(i = 0; i < tableSize; i++)
    {
        cout << "Enter value " << (i + 1) << " : ";
        cin >> table[i];
    }
    cout << "\n";

    //sort values
    qsort((void*)table, tableSize, sizeof(table[0]), sortFunction);

    //print the results
    for(i = 0; i < tableSize; i++)
    {
        cout << "Value " << (i + 1) << " : " << table[i] << endl;
    }

    cout << "\nDone\n";

    return 0;
}

int sortFunction(const void *a, const void *b)
{
    int intOne = *((int*)a);
    int intTwo = *((int*)b);

    if (intOne < intTwo)
    {
        return -1;
    }
    if (intOne == intTwo)
    {
        return 0;
    }

    return 1;    
}

Answer 1

如果您查看对 qsort 的实际调用...

qsort((void*)table, tableSize, sizeof table[0], sortFunction); 

...您会看到它提供：

• 一个 void* 地址和整个的大小（以字节为单位）要排序的数据数组，然后
• 是该数组中一个数据元素的大小，然后
• 是指向比较函数“sortFunction”的指针。

没有传递任何参数让 qsort 知道元素的类型 - 即如何使用任何单个数据元素中的各个位来表示某些数据值 - 所以qsort 无法有意义地比较两个这样的元素。当您提供...

int sortFunction(const void *a, const void *b)   
{   
    int intOne = *((int*)a);   
    int intTwo = *((int*)b);   

...并且 qsort 调用它时，您将获得两个指针 - 它们指向内存地址，但是当 qsort 调用 sortFunction< /code> 这些 void 指针仍然无法告诉您有关数据元素类型的任何信息，因为 qsort 本身没有任何可传递的洞察力。上面的最后两行代码是您（协调 qsort 调用的程序员）重新应用您一直以来所掌握的有关数据元素类型的知识：在本例中，它们是 < code>ints，因此您将每个 void* 转换为 int* （使用 (int*)a），然后取消引用该 int* 以获取内存地址 a 处的 int。对于b 也是如此。这样，您就恢复了原来存在的两个数字。作为数字。然后，sortFunction 的作用是指示排序完成后应如何对它们进行排序。为了指示 a 应该排在第一位，sortFunction 可以返回任何负值（例如 -1）；如果它们相等，则返回 0;，如果 b 应该是第一个，则返回任何正值（例如 1）。 qsort() 接收该信息并使用它来计算出如何在排序时对数据元素进行打乱。

FWIW，C 可以让您更简洁地表达为...

return intOne < intTwo ? -1 :
       intOne == intTwo ? 0 :
       1;

...或（更快，但依赖于布尔比较结果为 0 和 1，这可能会让一些阅读您代码的程序员感到困惑）... ...

return (intOne > intTwo) - (intOne < intTwo);

或者，如果您确定以下内容在数学上永远不会小于INT_MIN（此类值不恰当地环绕为一个大的正数）...

return intOne - intTwo;

Answer 2

sortFunction 实际上并不进行排序，它被用作比较函数来确定排序列表中一个元素是否应该在另一个元素之前。

Answer 3

您所谓的“sortFunction”通常称为比较器。它基本上告诉 qsort() 中的通用排序代码正在排序的数组中的两个元素是否比较相等 (0)，或者第一个参数是否在第二个 (<0) 或第一个参数之前排序在第二个之后排序 (>0)。

有了这些信息，再加上每行的大小、数组中的行数和数组的开头，qsort() 函数就可以正确地对数据进行排序。

Answer 4

正如您在文档中看到的，qsort函数采用比较器作为它的最后一个参数。该函数用于实际比较参数（告诉哪个参数应该在排序数组中排在第一位）。