我的通用快速排序有什么问题？

Question

我正在尝试编写通用快速排序：

void _qsort(void *ptr, 
        size_t lrange, 
        size_t rrange,
        size_t size,
        int (*cmp)(const void *, const void *))
{
    if (lrange < rrange) {
        size_t i, j;
        void *key;

        key = malloc(size);
        i = lrange;
        j = rrange;
        memcpy(key, ptr + i * size, size);
        while (i < j) {
            while (i < j && (*cmp)(ptr + j * size, key) > 0)
                j--;
            if (i < j) {
                memcpy(ptr + i * size, ptr + j * size, size);
                i++;
            }
            while (i < j && (*cmp)(key, ptr + i * size) > 0)
                i++;
            if (i < j) {
                memcpy(ptr + j * size, ptr + i * size, size);
                j--;
            }
        }
        memcpy(ptr + i * size, key, size);
        _qsort(ptr, lrange, i - 1, size, cmp);
        _qsort(ptr, i + 1, rrange, size, cmp);
    }
}

我在 int 数组上写了一个简单的测试，这是 cmp 函数：

int cmp(const void *x, const void *y)
{
    return *(int *)x - *(int *)y;
}

它导致核心转储，但是当我将 lrange, rrange, i, j 的类型从 size_t 更改为 int 时，它运行正确，我无法理解，为什么？

Answer 1

memcpy(key, ptr + i * size, size);

ptr是一个void *，你不能用void *进行指针运算，切换到char *（标准库中的qsort ).

Answer 2

size_t i, j;

是无符号类型。如果无符号变量的值为 0，并且减去 1，则该值将回绕到该无符号类型的最大可能值。

这可能发生在以下行：

j--;

和：

_qsort(ptr, lrange, i - 1, size, cmp);

当该无效值用作数组的索引时，将导致段错误，因为程序无法读取越界地址。

不要使用前缀为 _、_qsort 的名称，因为它们是为实施保留的。

我的通用快速排序有什么问题？

What's wrong with my generic quick sort?

c

quicksort