qsort 实现的一种方式如下:
void quick_sort(int *a, int n) {
if (n < 2)
return;
int p=a[n / 2];
int *l = a;
int *r = a + n - 1;
while (l <= r){
if (*l <= p) { // *l < p WORK WELL, BUT LIKE THIS *l <= p CANNOT GET IT .
l++;
continue;
}
if (*r > p) {
r--;
continue;
}
int t = *l;
*l++ = *r;
*r-- = t;
}
quick_sort(a, r - a + 1);
quick_sort(l, a + n -l);
}
看来,如果(*l < p)
当值等于 p
时,条件将左右交换
但是,只需使条件等于 p
,所以它会忽略相等的值。
为什么要*l
不能等于 p
?
最佳答案
正如@BLUEPIXY 所暗示的:“考虑所有元素具有相同值的情况。”
下面将简单地增加l
直到刚好超过r
。 while 循环将在 不更改 r
的情况下退出。
while (l <= r){
if (*l <= p) { // *l < p WORK WELL, BUT LIKE THIS *l <= p CANNOT GET IT .
l++;
continue;
}
...
}
然后调用下面的,这与quick_sort(a, n)
的父调用相同——无限递归。
// int *r = a + n - 1;
// r - a + 1 is the same as (a + n - 1) - a + 1 the same as n
quick_sort(a, r - a + 1);
关于c - qsort,比较中间值,为什么不能相等?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/20799811/