臭虫例如快速排序（K＆安培; R C书）？ [英] Bug in quicksort example (K&R C book)?

问题描述

这是快速排序应该排序V [左] ... v [右]为增加令;由K＆放从C编程语言复制（没有评论），R（第二版）：

This quicksort is supposed to sort "v[left]...v[right] into increasing order"; copied (without comments) from The C Programming Language by K&R (Second Edition):

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);
}

我觉得有一个错误在

I think there's a bug at

(left + right) / 2

假设左= INT_MAX - 1，右= INT_MAX。这是不是导致不确定的行为，由于整数溢出？

Suppose left = INT_MAX - 1 and right = INT_MAX. Wouldn't this result in undefined behavior due to integer overflow?

推荐答案

是的，你说得对。您可以使用左转 - （左 - 右）/ 2 来避免溢出

Yes, you're right. You can use left - (left - right) / 2 to avoid overflows.

这篇关于臭虫例如快速排序（K＆安培; R C书）？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！