java - 快速排序困惑

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

但是教程使用Quicksort(A, f,pivot_index);。

我 200% 确定更改“pivot_index-1”不会提高任何性能或降低复杂性；但只是想知道我的理解是否正确。

2)实现here作品;但它不会在每次传递时将枢轴元素放置在正确的位置。

Answer 1

我见过的两种实现:

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

Quicksort(A, f,pivot_index-1); 适用于第一种情况。

Quicksort(A, f, hub_index); 适用于第二种情况。

在第一种情况下执行 Quicksort(A, f, hub_index); 仍会产生排序列表，但会做一些额外的工作。

在第二种情况下执行Quicksort(A, f,pivot_index-1);可能不会始终得到完全排序的列表。

this implementation 的分析:

我可以明白它为什么起作用(它将用较低索引处的更大元素交换枢轴)，但这不是我所知道的快速排序，而且它可能会比所需的工作稍微多一些。