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. 如何处理十亿数据？
2. 这种排序算法（合并和排序）在其他语言（如 C#、python）中花费的时间更少......这是哈斯克尔语言的问题吗
3. 如何使用算法的复杂性来预测算法的运行时间？

Answer 1

快速排序的最坏情况是 n²。您的实现使用第一个元素作为透视，这会导致输入排序（或反向排序）时最坏情况下的性能。

要使快速排序以 n log n 的预期复杂度执行，您需要随机透视选择，或者在排序之前随机随机排列输入。