快速排序索引问题

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

快速排序索引问题

Quicksort index issue

c++

quicksort