快速排序混淆

我正在瀏覽快速排序和我看到的任何文章，我越來越困惑。快速排序混淆

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

快速排序混淆

回答

相關問題