c - K&R 的 qsort() 实现中 swap(v, left, (left + right)/2) 的目的是什么？

Question

在 K&R 第二版，第 5.11 节，第 107 页:

void qsort(void *v[], int left, int right, int (*comp)(void *, void *)) 
{
    int i, last;
    void swap(void *v[], int, int);
    if (left >= right)
        return;
    swap(v, left, (left + right)/2);
    last = left;
    for (i = left+1; i <= right; i++)
        if ((*comp)(v[i], v[left]) < 0) /* Here's the function call */
            swap(v, ++last, i);
    swap(v, left, last);
    qsort(v, left, last-1, comp);
    qsort(v, last+1, right, comp);
}

但是，我对“swap(v, left, (left + right)/2);”感到困惑。我觉得没用……这句话的目的是什么？

Answer 1

如果没有这句话，数组V[ ]是随机数据也没有问题。但是，如果 V[ ] 是排序数据，则不会遇到交换，并且变量 last 没有改变。因此，最后一个 qsort() 等价于 qsort(v, left+1, right, comp)。这意味着在递归调用中只减少了一个元素。当函数中比较次数为n时，比较需要n + (n-1) + (n-2) + ... + 1 = n(n+1)/2次才能完成。如果 n 很大，则需要很长时间。此外，如果 V[ ] 非常大，可能会遇到堆栈溢出错误。该声明的存在是为了防止它们。
另外，(left + right)/2应该是left + (right - left)/2以防止溢出错误。