我正在尝试将 qsort 算法实现为 C 中的通用函数

Question

我的函数返回一个排序数组，但它不是正确的数组：一些元素是重复的，另一些元素被删除了。 例如，预期返回值：

[93,13,73,30,79,31,95,22,26,1]

是：

[1,13,22,26,30,31,73,79,93,95]

我得到这个：

[1,1,22,26,26,26,30,30,95,95]

我的代码是：

int partitiong(size_t width, void *T, int d, int f, int 
    (*compareFunction)(const void *, const void *)) {

    uint8_t *Toctet = T;
    //uniform draw in set [d,...,f]
    uint32_t indice_swap = (rand() % (d - f - 1)) + d;

    //We swap T[f] and T[indice_swap]
    uint8_t *y = malloc(width);
    // y <-- T[indice_swap]
    memcpy(y, (Toctet + indice_swap * width), width);
    // T[indice_swap] <-- T[f]
    memcpy((Toctet + indice_swap * width), (Toctet + f * width), width);
    // T[f] <-- T[indice_swap]
    memcpy((Toctet + f * width), (T + indice_swap * width), width);

    uint8_t *x = malloc(width);
    memcpy(x,Toctet + f * width, width);

    int n = f;
    for (int i = f - 1; i >= d; i--) {
        //compare (T[i],x)
        if (compareFunction((Toctet + i * width), x))
        {
            //T[n] <-- T[i]
            memcpy((Toctet + n * width), (Toctet + i * width), width);
            //T[i] <-- T[n-1]
            memcpy((Toctet + i * width), (Toctet + n * width - width), width);
            n--;
        }
    }
    //T[n] <-- x
    memcpy((Toctet + n * width), x, width);

    //free of allocate variable
    free(y);
    free(x);

    return n;
}

void recqsortg(void *array, size_t elementSize, int (*compareFunction)(const void *, const void *),int d, int f) {
    if (f > d) {
        int n = partitiong(elementSize, array, d, f, compareFunction);

        recqsortg(array, elementSize, compareFunction, d, n - 1);
        recqsortg(array, elementSize, compareFunction, n + 1, f);
    }
}

void qsortg(void *array, size_t elementCount, size_t elementSize, int (*compareFunction)(const void *, const void *)) {
    recqsortg(array, elementSize, compareFunction, 0, elementCount - 1);
}

我真的不明白我的错误在哪里，我花了一整天的时间使用 gdb 来解决这个问题：c

Answer 1

您没有显示在测试中使用的比较函数，并且该问题没有记录比较函数的预期行为。此类函数的通常约定是标准库的

qsort()

函数，该函数根据第一个参数是否小于、等于，期望比较函数的返回值小于 0、等于 0 或大于 0 ，或大于第二个。

如果这也是您的期望，那么您的

partitiong()

函数错误地使用了比较函数。使用传统的比较功能，这...

        if (compareFunction((Toctet + i * width), x))

...询问元素

i

是否不等于主元值，但你实际上想问的是它是否大于主元值。那将是：

        if (compareFunction((Toctet + i * width), x) > 0)

此外，你的随机主元选择公式是有问题的。考虑：

    uint32_t indice_swap = (rand() % (d - f - 1)) + d;

d

是子数组下界的索引，

f

是上界的索引。那么，您应该预期

d - f - 1

将为负数。由于

rand()

将返回非负数，因此在 C 中，

%

运算符返回其操作数的代数商，并截断任何小数部分。除其他外，这意味着当操作数符号相反时结果为负。因此，您选择的主元位于您尝试排序的子数组之外，并且可能完全位于输入数组之外。你想要这个，而不是：

    uint32_t indice_swap = (rand() % (f - d + 1)) + d;

通过这两项更改，我能够在代码中使用传统风格的比较函数来获得示例输入数组的正确排序。