haskell中整数的快速排序

Question

haskell库中有用O(n)时间排序整数的函数吗？所谓，O(n)，我的意思是比比较排序更快，而且对整数是特定的。

基本上，我发现下面的代码在排序方面花费了很多时间(与不进行排序的列表之和相比)：

import System.Random
import Control.DeepSeq
import Data.List (sort)

genlist gen = id $!! sort $!! take (2^22) ((randoms gen)::[Int])

main = do
    gen <- newStdGen
    putStrLn $ show $ sum $ genlist gen

对列表进行求和并不需要deepseq，但我尝试的是什么，但是上面的代码对于我正在寻找的指针来说已经足够好了。

时间:6秒(没有排序)；大约35秒(带排序)

内存:大约80 MB (没有排序)；大约310 MB (带有排序)

注释1:对于我来说，内存是一个比时间更大的问题，因为我手头的任务是摆脱内存错误(内存使用量变成3GB！)在运行30分钟后)

我假设更快的算法也将提供打赌内存打印，因此寻找O(n)时间。

注2 :我正在寻找Int64的快速算法，尽管其他特定类型的快速算法也会有帮助。

使用的解决方案:带未装箱向量的 IntroSort对我的任务来说已经足够好了：

import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Algorithms.Intro as I

sort :: [Int] -> [Int]
sort = V.toList . V.modify I.sort . V.fromList

Answer 1

为此，我会考虑使用向量而不是列表，因为列表每个元素都有很大的开销，而未装箱的向量本质上只是一个连续的字节块。向量算法包包含可以用于此的各种排序算法，包括基类，在您的情况下，我希望它能做得很好。

这里有一个简单的例子，但是如果您计划对结果进行进一步的处理，那么将结果保持为向量形式可能是个好主意。

import qualified Data.Vector.Unboxed as V
import qualified Data.Vector.Algorithms.Radix as R

sort :: [Int] -> [Int]
sort = V.toList . V.modify R.sort . V.fromList

此外，我怀疑您的示例中有很大一部分运行时间来自随机数生成器，因为标准生成器并不是以其性能而为人所知的。您应该确保只对排序部分进行计时，如果程序中需要大量随机数，则有更快的生成程序可用。

Answer 2

这是从理查德·伯德的书“函数算法设计的皮尔斯”中摘录的(尽管我不得不编辑它一点，因为书中的代码并没有像写的那样编译)。

import Data.Array(Array,accumArray,assocs)  

sort :: [Int] -> [Int]
sort xs = concat [replicate k x | (x,k) <- assocs count]
        where count :: Array Int Int 
              count = accumArray (+) 0 range (zip xs (repeat 1))
              range = (0, maximum xs)

它的工作方式是创建一个按整数索引的数组，其中的值是每个整数在列表中出现的次数。然后它创建一个索引列表，根据计数重复它们在原始列表中发生的相同次数。

您应该注意到，它与列表中的最大值是线性的，而不是列表的长度，因此像[ 2^x | x <- [0..n] ]这样的列表不会被线性排序。