快速排序混乱

Question

我正在进行快速排序，无论看到哪篇文章，我都会更加困惑。

1） 这个实现真的很好http://gauss.ececs.uc.edu/Courses/C321/html/quicksort.java.html

但据我所知，每次传球后，支点指数都在正确的位置。

那么理想情况下，我们应该做以下事情：

   public static void Quicksort(int A[], int f, int l)
   {
      if (f >= l) return;
      int pivot_index = partition(A, f, l);
      Quicksort(A, f, pivot_index-1); //*** pivot_index-1
      Quicksort(A, pivot_index+1, l);
   }

但教程使用了快速排序（A，f，pivot_index）。

我有200%的把握，更改"pivot_index-1"不会提高任何性能或降低复杂性；但我只是想弄清楚我的理解是否正确。

2） 这里的实施是有效的；但它并没有在每次传球时将枢轴元件放置在正确的位置。

Answer 1

我看到的两个实现：

• 包含结束索引
• 结束索引独占

CCD_ 1用于第一种情况。

CCD_ 2用于第二种情况。

对第一种情况执行Quicksort(A, f, pivot_index);仍然会得到一个排序列表，但会做一些额外的工作。

对第二种情况执行Quicksort(A, f, pivot_index-1);可能不会一直产生完全排序的列表。

此实现的分析：

我能理解为什么它能工作（它将在较低的索引处用较大的元素交换枢轴），但我知道这不是QuickSort，它可能做的工作比所需的略多。