C - 自定义 qsort 不工作

Question

我正在尝试创建一个具有相同参数的 qsort 类型的函数。我还写了 3 个函数来比较 int、float 和字符。由于某种原因，它在任何情况下都不起作用。我不知道这是否是我的 qsortx 函数的问题，但我检查了几次，它应该工作得很好。我不确定问题出在哪里，或者我做错了什么。我目前正在学习函数指针，我可能还没有掌握与之相关的所有内容。提前致谢。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

void qsortx(void*, int, int, int (*)(const void*, const void*));
int intcmp();
int floatcmp();
int charcmp();

int main()
{
    int i,n;
    char items[]={'c', 'a', 'b'};
    n = 3;
    for (i=0;i<n;++i) {
        printf("%c ", items[i]);
    }
    printf("\n");

    qsortx(items, n, sizeof(char), charcmp);

    for (i=0;i<n;++i) {
        printf("%c ", items[i]);
    }
    printf("\n");
    return 0;
}

void qsortx (void *tp, int length, int pace, int(*fp)(const void* a, const void* b)) {
    int switched,i,j;
    void *p;
    p=(void*)malloc(pace);
    switched = 1;
    while (1) {
        if (switched == 0) {
            return;
        }
        switched = 0;
        for (i=0; i<length-1;++i) {
            for (j=0;j<length-1;++j) {
                printf("%c %c", tp+i, tp+j);
                if (fp(tp+i, tp+j) > 0) {
                    memcpy(p, tp+i, pace);
                    memcpy(tp+i, tp+j, pace);
                    memcpy(tp+j, p, pace);
                    switched++;
                }
            }
        }

    }
}

int intcmp(const void* a, const void* b) {
    return *(int*)a - *(int*)b;
}

int floatcmp(const void* a, const void* b) {
    return *(float*)a - *(float*)b;
}

int charcmp(const void* a, const void* b) {
    return *(char*)a - *(char*)b;
}

Answer 1

您有多个与指针算法和元素大小相关的问题。您的排序也有逻辑错误(我猜您知道这是单向振动器排序)。下面是修复这些缺陷的 qsortx() 函数的一个版本:

void qsortx (void *tp, int length, int pace, int(*fp)(const void* a, const void* b)) {
    if (length > 1) {
        char *bound = ((char *) tp) + (length * pace);
        char *p = malloc(pace);
        char *item1p;

        for (item1p = tp; item1p < (bound - pace); item1p += pace) {
            char *item2p;

            for (item2p = item1p + pace; item2p < bound; item2p += pace) {
                if (fp(item1p, item2p) > 0) {
                    memcpy(p, item1p, pace);
                    memcpy(item1p, item2p, pace);
                    memcpy(item2p, p, pace);
                }
            }
        }

        free(p);
    }
}

注意:

1. 所有指针算法都是在 char * 类型的值上执行的。
2. 在遍历输入数组时必须考虑元素大小(pace)，否则只会打乱数据。
3. 最内层的循环应该从下一个外层循环中考虑的元素之后开始。
4. switched = 1 是比 switched++ 更好的选择，因为它不会溢出，而您关心的只是零与非零。 (更新:但 switched 不再相关。)
5. (更新)如果通过 item1p 循环导致零交换，则提前退出是不正确的。仅仅因为一个元素已经在其正确位置并不意味着所有后续元素也都在其正确位置。我更新了上面的代码以删除该行为。
6. (更新)正如 chux 所观察到的，为交换元素保留的临时空间没有被释放。我添加了一个适当的 free(p)。
7. (更新)我还以数组长度大于 1 为条件进行排序，这避免了在 length 为零。