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

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

假设 left = INT_MAX - 1，right = INT_MAX。这样会导致整数溢出而产生未定义的行为吗？

- functionptr

---

它可能是基于一个假设来编程的，即在运行时数组不会太大。 :) - sarnold

这是一个非常好的假设，因为你在内存中不会有足够的空间来运行你的快速排序程序。 - Karoly Horvath

请参见：http://googleresearch.blogspot.com/2006/06/extra-extra-read-all-about-it-nearly.html - Pascal Cuoq

@functionptr，您能否回答这个问题吗？ http://stackoverflow.com/questions/24534487/quick-sort-programmed-in-c - HELP PLZ

Answer 1

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

- Artefact2

---

@Jerry / Paul：由于 (right - left) == - (left - right)，因此与本答案的表述相同。 - caf

@caf：啊，我没有想到这个角度，但你是对的。我撤回我的原始评论，并为我的迟钝道歉。 - Jerry Coffin

Answer 2

你不是想象一个有 INT_MAX 个元素的数组，对吧？

- Armen Tsirunyan

---

那只是假设使用32位整数，留给地址空间不到8GB。在现代硬件上完全没有问题 :) - sarnold

我们可能要原谅K＆R没有考虑到内存从kB增长到GB。还有“640k应该足够每个人使用”？ - Bo Persson

@Bo，你知道有些平台使用16位的int，而且我很确定其中一些平台的内存超过了64Kb。int != intptr_t。 - Karl Knechtel

Answer 3

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。

- Hans Passant

---

__cdecl 这个问题不是标准定义的一部分。 - caf

我确信这是真的，那时他们可能只有一种调用约定。而且关键字也少得多，很少以两个下划线开头。让厂商将其变得复杂。必须如此，标准有点烂。 - Hans Passant

Answer 4

是的，你说得对，虽然可能只是为了简单起见而这样写--毕竟它只是一个示例，而不是生产代码。

- Peter Alexander