c++ - 使用 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 知道元素的类型是什么 - 即如何使用任何单个数据元素中的各个位来表示某些数据value - 所以 qsort 无法有意义地比较两个这样的元素。当你供应...

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

...并且 qsort 调用它，您得到两个指针 - 它们指向内存地址但是当 qsort 调用 sortFunction那些 void 指针仍然没有告诉您有关数据元素 type 的任何信息，因为 qsort 本身没有要传递的信息。上面最后两行代码是您(协调 qsort 调用的程序员)重新应用您一直以来所掌握的关于数据元素类型的知识:在这种情况下，它们是 int，因此您将每个 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;

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

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

...或者，如果您确定以下在数学上永远不会小于INT_MIN(这样的值不恰本地环绕成一个大的正数)。 .

return intOne - intTwo;