尋找澄清快速排序的算法複雜

Question

有人能解釋爲什麼快速排序的最好情況運行時不是線性的？有沒有辦法使quicksort linear的最佳運行時間？如果是這樣，爲什麼他們通常不用於實踐？

Answer 1

你應該至少通過維基鏈接已經消失了......他們都與圖ñ動畫這是很容易理解這種解釋。

http://en.wikipedia.org/wiki/Quicksort

Answer 2

快速排序運行在爲O（n 2 ）時間最壞的情況下，但最好/平均爲O（n log n）的。儘管它的最壞情況更嚴重，但它在實踐中表現優於排序和合並排序（最差情況下的O（nlogn）排序）。

排序只能在線性時間內運行，除非它們已經排序，並且這僅適用於排序的最好情況爲O（n），如insertion sort。

Answer 3

當然，你可以先檢查輸入是否已排序，並立即返回，如果它是。這產生了具有線性最佳情況複雜度的算法。但是最後你會得到一個「Modified Quicksort」而不是「Quicksort」。

Answer 4

快速排序是直接比較分選方法。每個這樣的方法在每個步驟上使用二元決策（即直接比較）以在分類的兩個可能結果之間分支。所有可能的N個元素數組的排序都是N！並且因此能夠輸出這些結果中的每一個的二叉決策樹的最低高度是log（N！），但可以證明，儘管O（log（N！））= O（N *日誌（N））。所以沒有直接比較排序算法可能比這個算法複雜得多。

因此，如快速排序是這樣的算法的一個例子其可以從不具有比O（N *日誌（N））的複雜性較低，所以它不能是線性的。