快速排序在排序列表上花費更長時間

-4

我運行了一些測試，發現quicksort實際運行速度越慢，列表排序越清晰，這相當反直覺！我已閱讀維基百科上的quicksort算法，但我不明白爲什麼需要更長的時間排序越多。任何幫助，將不勝感激！快速排序在排序列表上花費更長時間

2013-05-16 clay

如果您需要幫助，請發佈您的代碼。我也認爲這個問題更適合[程序員]（http://programmers.stackexchange.com/）。 – Renan

基本上在一個排序列表中，快速排序將在開始時將緩衝列表。 – njzk2

維基百科文章的這一特定部分解釋了最壞情況下的計算http://en.wikipedia.org/wiki/Quicksort#Average-case_analysis_using_recurrences – njzk2

非隨機快速排序通常會選擇第一個元素作爲主元素;當列表已經排序時，這將導致列表被分成一個空的左側列表和右側列表，其中包含n-1元素。相同的行爲將在每次遞歸調用發生，並且總運行時間將是Ñ + n-1個 + N-2 + ... + 1 =爲O（n^2）。

2013-05-16 12:58:04

如果您要保證O（nlogn），請使用中位數作爲pivot選擇 – Daniel

@Daniel - 如果要保證O（n log n），使用mergesort或heapsort會更有意義。中位數的中位數可能會給你你的漸近保證（我沒有進行雙重檢查），但它很複雜，常數因素也很差。 – Steve314

@ Steve314，我知道有一些開銷，但由於我從來沒有在實際中使用它，我不知道有多少。感謝提示:) – Daniel

你指的是QuickSort的一個衆所周知的問題。解決問題的一個方法是使用除第一個元素之外的元素作爲主元素。

本文去深入得多，路程大約需要爲已排序列表和途徑問題落實的工作這種快速排序異常。 http://www.csie.ntu.edu.tw/~b93076/p847-sedgewick.pdf

2013-05-16 13:04:23

回答