0

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

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）这里的实现有效；但它不会在每次传递时将枢轴元素放置在正确的位置。

4

1 回答 1

2

我见过的两个实现：

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

Quicksort(A, f, pivot_index-1);是针对第一种情况。

Quicksort(A, f, pivot_index);是针对第二种情况。

Quicksort(A, f, pivot_index);对第一种情况进行操作仍会产生排序列表，但会做一些额外的工作。

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

这个实现的分析：

我可以看到它为什么起作用（它会用较低索引处的较大元素交换枢轴），但这不是我所知道的快速排序，它可能比需要做的工作略多。

于 2013-02-20T17:33:31.250 回答