我正在尝试编写一个通用的快速排序:
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
时,它跑对了,我不明白,为什么?
最佳答案
size_t i, j;
是无符号类型。如果无符号变量的值为 0,并且减去 1,则该值将回绕到该无符号类型的最大可能值。
这可能发生在线路上:
j--;
和:
_qsort(ptr, lrange, i - 1, size, cmp);
当该无效值用作数组的索引时,它将导致段错误,因为程序无法读取越界地址。
不要使用前缀为 _
、_qsort
的名称,因为这些是为实现保留的。
关于c - 我的通用快速排序有什么问题?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/36310722/