在 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);”感到困惑。我觉得没用……这句话的目的是什么?
最佳答案
如果没有这句话,数组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
以防止溢出错误。
关于c - K&R 的 qsort() 实现中 swap(v, left, (left + right)/2) 的目的是什么?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/27586054/