8

这种快速排序应该将“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。由于整数溢出，这不会导致未定义的行为吗？

4

4 回答 4

7

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

于 2011-06-26T21:47:57.400 回答
2

你不是在想象一个有INT_MAX许多元素的数组，是吗？

于 2011-06-26T21:47:59.147 回答
1

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

于 2011-06-26T21:49:58.973 回答
1

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 因为你不知道你在排序什么类型。

于 2011-06-26T22:30:19.343 回答