我正在浏览quicksort,无论我看到哪一篇文章,我都会感到更加困惑。

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,ivot_index);。

我200%确信进行更改'pivot_index-1'不会提高性能或降低复杂性;但是只要我的理解是正确的,就想做出。

2)实现here有效;但是每次旋转都不会将枢轴元素放置在正确的位置。

最佳答案

我见过两个实现:


包含结束索引
结束索引排他


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

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

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

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

this implementation的分析:

我可以看到它为什么起作用(它将在较低的索引处用更大的元素交换枢轴),但这不是我所知道的QuickSort,它可能会比所需的做更多的工作。

10-07 19:52
查看更多