快速排序示例（K&RC 书）中的错误？

Question

此快速排序应该将“v[left]...v[right] 排序为递增顺序”；复制（无注释）自 K&R 的《C 编程语言》（第二版）：

void qsort(int v[], int left, int right)
{
    int i, last;
    void swap(int v[], int i, int j);

    if (left >= right)
        return;
    swap(v, left, (left + right) / 2);
    last = left;
    for (i = left+1; i <= right; i++)
        if (v[i] < v[left])
            swap(v, ++last, i);
    swap(v, left, last);
    qsort(v, left, last-1);
    qsort(v, last+1, right);
}

我认为假设 left = INT_MAX - 1 且 right = INT_MAX 存在错误

(left + right) / 2

。这不会导致由于整数溢出而导致未定义的行为吗？

Answer 1

是的，你说得对。您可以使用left - (left - right) / 2来避免溢出。

Answer 2

您不会想象一个具有 INT_MAX 个元素的数组，对吗？

Answer 3

是的，你是对的，尽管它可能只是为了简单起见而这样写——毕竟它是一个示例，而不是生产代码。

Answer 4

K&R 在使用无符号与有符号参数方面总是有点草率。我认为使用只有 16 KB 内存的 PDP 会产生副作用。不久前已经修复了。 qsort的当前定义是

void qsort(
   void *base,
   size_t num,
   size_t width,
   int (__cdecl *compare )(const void *, const void *) 
);

注意使用size_t而不是int。当然还有 void* base 因为你不知道你要排序的类型。