这个快速排序应该将“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,last);
qsort(v,last-1);
qsort(v,last+1,right);
}
我觉得有一个错误
(left + right) / 2
假设left = INT_MAX – 1且right = INT_MAX.由于整数溢出,这不会导致未定义的行为吗？
解决方法
你是对的.您可以使用左 – (左 – 右)/ 2来避免溢出.
