c++ - 快速排序索引问题

Question

我正在尝试实现基本的快速排序功能。我对索引范围有点困惑。

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)

它没有。

不是一样的范围吗？有什么意义？

Answer 1

由于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);