快速排序示例中的错误（K＆R C书）？

这个快速排序应该将“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 + right) / 2 

假设left = INT_MAX – 1且right = INT_MAX。 由于整数溢出，这不会导致未定义的行为吗？

Answer 1

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

Answer 2

您不是在想象一个具有INT_MAX数量元素的数组，不是吗？

Answer 3

是的，你是对的，虽然它可能只是为了简单而写的 – 毕竟这是一个例子，而不是生产代码。

Answer 4

使用unsigned vs signed参数时，K＆R总是有点草率。 我认为使用只有16千字节内存的PDP的副作用。 这已经被修复了一段时间。 qsort的当前定义是

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

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