c - 快速排序示例(K&R C 书)中的错误？

Question

这个快速排序应该将“v[left]...v[right] 排序为递增顺序”；从 K&R 的 The C Programming Language(第二版)复制(无注释):

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 + right) / 2

假设左边 = INT_MAX - 1，右边 = INT_MAX。这不会由于整数溢出而导致未定义的行为吗？

Answer 1

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