使用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*地址和要排序的整个数据数组的大小(以字节为单位)，然后
• 该数组中一个数据元素的大小，然后
• 一个指向比较函数的指针

传递的参数不允许qsort知道元素的类型-即如何使用任何单个数据元素中的单个位来表示某个数据值-因此qsort无法有意义地比较两个这样的元素。当你提供..。

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

当...and qsort调用它时，你会得到两个指针-它们指向内存地址，但是当qsort调用sortFunction时，这些void指针仍然不会告诉你任何关于数据元素类型的信息，因为qsort本身没有可传递的洞察力。在上面的最后两行代码中，您--协调qsort调用的程序员--重新应用了您一直掌握的关于数据元素类型是什么的知识:在本例中，它们是int，所以您将每个void*转换为一个int* (使用(int*)a)，然后取消对该int*的引用，以获得内存地址a处的int。b也是如此。在这样做的时候，您已经恢复了作为数字存在的两个数字。然后，sortFunction的工作是指示排序完成时它们应该如何排序。为了指示a应该是第一个，sortFunction可以返回任何负值(例如-1)；如果它们相等，则返回return 0;；如果b应该是第一个，则返回任何正值(例如1)。qsort()接收这些信息，并使用它来确定如何在排序时打乱数据元素。

FWIW，C可以让你更简洁地表达这一点...

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

...or (速度更快，但依赖于布尔比较结果为0和1，这可能会使一些程序员在阅读您的代码时感到困惑)...

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

...or，如果您确定下面的值在数学上永远不会小于INT_MIN (这样的值不适当地绕回到一个大的正数)……

return intOne - intTwo;

Answer 2

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

Answer 3

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

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