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。您的实现使用第一个元素作为数据透视表，当输入被排序（或反向排序）时，会导致最差情况下的性能。

要获得快速排序在ň日志ň其预期的复杂性来执行，你需要或者随机的选择转动或排序之前，随机混合输入。