快速排序混淆

我正在浏览快速排序和我看到的任何文章，我越来越困惑。快速排序混淆

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）执行here有效;但并不是每次传递都会将主元素放置在正确的位置。

来源

2013-02-20 Jack

看看这里http://xoax.net/comp_sci/crs/algorithms/lessons/Lesson4/ – Arpit 2013-02-20 17:00:50

两个实现我见过：

结束索引包括
结束索引独家

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

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

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

对第二种情况做Quicksort(A, f, pivot_index-1);可能不会导致一个完全排序的列表。

的this implementation分析：

我可以看到，为什么它的工作原理（它会掉以较低的指标有较大元素的支点），但是这不是快速排序，我知道，它可能会稍微做比需要更多的工作。

来源

2013-02-20 17:33:31 Dukeling

据我所知，第一个链接的实现是End index Inclusive;因为它比较为：while（A [1]> pivot）l--;因此，在这种情况下使用'Quicksort（A，f，pivot_index-1）;'应该正确吗？ – Jack 2013-02-20 18:00:22

第一个链接的实现看起来相当破碎（我试着编译和测试它），但是，它似乎是包含性的，所以'Quicksort（A，f，pivot_index-1）'应该可以工作。 – Dukeling 2013-02-20 18:15:24

快速排序混淆

回答

相关问题