c - 使用 void 指针和类型参数的 C 中多种类型的排序函数

Question

在这个问题中，一个函数采用指向数组的 void 指针、元素数量和指示元素类型的整数来对数组进行排序。是否有任何技巧可以避免像以下解决方案那样编写 4 次相同的代码？

//type 1:short, 2:int, 3:float, 4:double
void Sort(void *values, int nValues, int type) {
    int i, j, temp;

    switch(type) {
    case 1: //short
    {
        short *ptr = (short *)values;
        for (i = 0; i < nValues - 1; i++)
            for (j = i; j < nValues; j++)
                if (ptr[i] > ptr[j]) {
                    temp = ptr[i];
                    ptr[i] = ptr[j];
                    ptr[j] = temp;
                }
        break;
    }
    case 2: // int
    {
        int *ptr = (int *)values;
        for (i = 0; i < nValues - 1; i++)
            for (j = i; j < nValues; j++)
                if (ptr[i] > ptr[j]) {
                    temp = ptr[i];
                    ptr[i] = ptr[j];
                    ptr[j] = temp;
                }
        break;
    }
    case 3: // float
    {
        float *ptr = (float *)values;
        for (i = 0; i < nValues - 1; i++)
            for (j = i; j < nValues; j++)
                if (ptr[i] > ptr[j]) {
                    temp = ptr[i];
                    ptr[i] = ptr[j];
                    ptr[j] = temp;
                }
        break;
    }
    case 4: // double
    {
        double *ptr = (double *)values;
        for (i = 0; i < nValues - 1; i++)
            for (j = i; j < nValues; j++)
                if (ptr[i] > ptr[j]) {
                    temp = ptr[i];
                    ptr[i] = ptr[j];
                    ptr[j] = temp;
                }
    }
    }
}

Answer 1

是的，还有一个选择。在C standard library there already is a function称为 qsort (这可能是快速排序的缩写，但也可以是任何其他排序算法)。要使用该函数，您需要将数组、数组中元素的数量、每个元素的大小和比较函数传递给它。

您只需为每种数据类型编写比较函数，如该页面上的示例所示。

如果要将 4 个比较函数合并为一个函数，则必须将一些上下文信息传递给比较函数。在那种情况下，您不能使用 qsort不再需要使用 qsort_s .那么您的比较函数可能如下所示:

#define compare(a, b) (((a) > (b)) - ((b) > (a)))
#define compare_ptr(type) (compare(*(type *)(p1), *(type *)(p2)))

static int compare_by_type(const void *p1, const void *p2, void *ctx) {
    int type = *(int *) ctx;
    switch (type) {
    case 1: return compare_ptr(short);
    case 2: return compare_ptr(int);
    case 3: return compare_ptr(float);
    case 4: return compare_ptr(double);
    default: return 0;
    }
}

#undef compare
#undef compare_ptr

int main(void) {
    int iarray[] = {1, 6, 4, 9, 55, 999, -33333};
    int sort_type = 1;

    qsort_s(iarray, 7, sizeof(int), compare_by_type, &type);
}

这是一些相当高级的东西:

• 传递函数指针
• 用指向任意类型的指针做指针的事情
• 使用接受类型名称作为宏参数的宏
• 混合 bool 运算和整数运算

但最后，向列表中添加更多类型是微不足道的，只要它们支持 <运营商。

请注意 float和 double甚至不属于这一类，因为他们的运营商 <返回 false只要其中一个数字是 NaN ，这意味着不是一个数字，并且来自 0.0 / 0.0 等表达式的结果.一旦数组中有这样的值，行为就会变得未定义。排序功能甚至可能陷入死循环。要解决此问题，请更改 compare 的定义宏观:

#define compare(a, b) (((a) > (b)) - !((b) <= (a)))

现在看起来更复杂，但适用于 NaN .例如:

compare(NaN, 5)
= (NaN > 5) - !(5 <= NaN)
= false - !(5 <= NaN)
= false - !(false)
= false - true
= 0 - 1
= -1

这意味着 NaN 将排序到数组的前面。

compare(NaN, NaN)
= (NaN > NaN) - !(NaN <= NaN)
= false - true
= -1

该死。比较两个 NaN 的结果应该是 0，这意味着它们相等。所以在这种特殊情况下需要更正:

#define compare(a, b) (((a) > (b)) - ((b) > (a)) - ((a) != (a) || (b) != (b)))

自 NaN是唯一与自身比较不相等的值，此附加代码不会影响整数运算，应由编译器优化掉。