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

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

size_t i, j;

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

这可能发生在线路上:

j--;

和:

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

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

---

不要使用前缀为 _、_qsort 的名称，因为这些是为实现保留的。