試圖導致「更壞的情況」快速排序

我在C中實現了快速排序實現，我試圖找出需要輸入什麼樣的輸入來導致更差的情況下性能。試圖導致「更壞的情況」快速排序

總是選擇在分區作爲樞軸的最後一個元素在上已排序的列表，或相同的元素的列表性能差（N^2）這樣的結果。

所以我試圖做到這一點，導致the following code。數據透視始終是最後一個元素，輸入是已經排序的列表。爲了證明覆雜度確實是n^2，我創建了一個全局變量，我在每次迭代中遞增，然後最終打印出來。

我預計該程序將打印：

Done in 64 iterations

然而，這樣做是在28次迭代。也許我對「複雜性」這個詞的理解是錯誤的？

2013-03-31 reish

n *（n-1）/ 2 = 8 * 7/2 = 28'。 'n *（n-1）/ 2'仍然是O（n^2）。 – nneonneo

@darwish英俊的頭像;） –

採取更大的輸入（如10^5元素），你會立即知道它是O（n^2）。 –

在每次迭代中，該列表會縮小一個元素，因爲該透視被移動並不再計數。因此，總迭代次數爲7 + 6 + 5 + 4 + 3 + 2 + 1 = 28.

請注意，這仍然是二次的，因爲它等於n*(n-1)/2。

2013-03-31 10:07:07 nneonneo

對於n = 8，迭代次數爲28。

迭代的數量等於n*(n-1)/2 = 8 * 7/2 = 28

現在函數是F（N）= N *（N-1）/ 2 = N 2 /2 - n/2。

有用於F（N）= O（N 2 /2 - N/2）= O（（1/2）N 2 ）= O（N 2 ）。

因此，您的輸入實際上是Quicksort最糟糕的情況。

2013-03-31 11:20:25 Deepu

回答