我正在尝试实现基本的快速排序功能。我对索引范围有点困惑。
void q_sort(int * tab, int left, int right)
{
if(left < right)
{
int piv = left;
for(int i = left+1; i <= right; ++i)
if(tab[i] < tab[left])
change(tab[++piv], tab[i]);
change(tab[piv],tab[left]);
q_sort(tab, left, piv-1);
q_sort(tab, piv+1, right);
}
}
让我们来看一个包含四个元素的数组。如果我用
调用函数q_sort(array, 0, 3)
它似乎可以工作,但如果我换行
for(int i = left+1; i < right; ++i)
调用函数
q_sort(array, 0, 4)
它没有。
不是一样的范围吗?有什么意义?
最佳答案
由于q_sort
是递归的,因此需要在两个上下文中理解其参数的含义:
- 当函数被外部调用时,
- 执行递归调用时。
您已经调整了外部调用q_sort(array, 0, 4)
中的int right
参数以将右端视为独占 ,但递归调用 q_sort(tab, left, piv-1)
假定第三个参数包含。从表达式中删除 -1
以解决此问题:
q_sort(tab, left, piv); // <<== Here
q_sort(tab, piv+1, right);
关于c++ - 快速排序索引问题,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/30378875/