haskell快速排序的複雜性？

Question

我運行下面的快速排序的Haskell功能（使用合併和排序算法）：

qsort []=[] 
qsort (x:xs) = 
    qsort smaller ++ [x] ++ qsort larger 
    where 
     smaller = [a | a <- xs , a<x ] -- edit 
     larger = [b | b <- xs , b>=x ] 

爲了測試運行時該數據的有點大金額，我運行下面的代碼：

qsort [100000,99999..0] 

它需要直到現在40分鐘，它仍在運行！即使是一個100,000的列表並不是那麼大，所以：

1. 我怎麼能處理數據十億的數據？這是一個在Haskell語言中的問題
2. 我怎麼能預測一個算法的運行時間使用其複雜性？

Answer 1

快速排序的最壞情況下的時間是^Ñ2。您的實現使用第一個元素作爲數據透視表，當輸入被排序（或反向排序）時，會導致最差情況下的性能。

要獲得快速排序在ň日誌ň其預期的複雜性來執行，你需要或者隨機的選擇轉動或排序之前，隨機混合輸入。