c - 我的快速排序无法正常工作。我做错了什么？

Question

我的 QuickSort 无法排序。我不明白为什么。当我进行两次排序时，它排序正确，但如果我们使用快速排序两次——它就不是快速排序。

<小时/>

我的任务是编写一个通用的快速排序函数，以便它可以对任何类型的数组进行排序。在函数中，我们给出了一个用于排序的字符串指针、字符串的长度、单个元素的大小以及比较函数。

我的比较功能:

int icmp(void* x, void* y)
{
    int a = *(int*)x;
    int b = *(int*)y;
    if (a > b) {
        return 1;
    }
    else if (a < b) {
        return -1;
    }
    else {
        return 0;
    }
}

我的交换功能:

void swapper(void* x, void* y, size_t size)
{
    char* a = NULL;
    if ((a = (char*)malloc(size * sizeof(char*))) == NULL) {
        return NULL;
    }
    for (int i = 0; i < size; i++) {
        a[i] = *((char*)x + i * sizeof(char*));
    }
    *(char*)x = *(char*)y;
    *(char*)y = *a;
}

我的排序功能:

void my_qsort(const void* ptr, size_t count, size_t size, int (*cmp)(const void*, const void*))
{
    sort(ptr, 0, count - 1, size, cmp);
}

void sort(const void* ptr, int low, int high, size_t size, int (*cmp)(const void*, const void*))
{
    int i = low;
    int j = high;
    char* mid = (char*)ptr + ((i + j) / 2) * size;
    while (i <= j)
    {
        while ((cmp((char*)ptr + i * size, mid) == -1)) {
            i++;
        }
        while (cmp((char*)ptr + j * size, mid) == 1) {
            j--;
        }
        if (i <= j) {
            swapper((char*)ptr + i * size, (char*)ptr + j * size, size);
            i++;
            j--;
        }
    }
    if (j > low) {
        sort(ptr, low, j, size, cmp);
    }
    if (i < high) {
        sort(ptr, i, high, size, cmp);
    }
}

1)输入指针:83 21 52 10 49 22 21 34 51 51

输出指针:10 21 21 22 34 49 51 52 51 83

2)输入指针:59 4 47 79 9 44 5 78 40 19

输出指针:4 5 9 19 40 44 47 59 78 79

3)输入指针:13 80 97 73 14 17 32 26 92 90

输出指针:13 14 73 17 26 32 80 90 92 97

Answer 1

问题的一部分来自于仅复制第一个字节的 swapper 函数。您可以将该函数重写为:

void swapper(void* x, void* y, size_t size)
{
    for(size_t i = 0; i < size; i++) {
        char tmp = ((char*)x)[i];
        ((char*)x)[i] = ((char*)y)[i];
        ((char*)y)[i] = tmp;
    }
}

这可以避免内存分配。注意:在离开函数之前内存没有被释放，因此也造成了内存泄漏。

问题的第二部分是在迭代时更改枢轴。实现它的一个简单方法是使用发现的算法 here :

void sort(const void* ptr, int low, int high, size_t size, int (*cmp)(const void*, const void*))
{
    int i = low;
    int j = high;
    char* pivot = (char*)ptr + low * size;
    while (i < j)
    {
        while ((cmp((char*)ptr + i * size, pivot) <= 0)) {
            i++;
        }
        while (cmp((char*)ptr + j * size, pivot) > 0) {
            j--;
        }
        if (i < j) {
            swapper((char*)ptr + i * size, (char*)ptr + j * size, size);
        }
    }
    swapper(pivot, (char*)ptr + j * size, size);
    if (j-1 > low) {
        sort(ptr, low, j-1, size, cmp);
    }
    if (j+1 < high) {
        sort(ptr, j+1, high, size, cmp);
    }
}