你如何在Haskell进行就地快速排序

Question

有人可以提供就地快速排序haskell功能吗？即它返回一个新的排序列表,但输入列表被复制到一个可变数组或其他东西.

我想看看如何做到这一点,因为我有一个性能关键程序,我需要模拟比赛和计数得分.如果我为此使用不可变数据结构,则每个种族将采用O(log(numRaces)+ numRunners)时间,而如果我使用可变数组等,则每个种族将采用O(log(numRaces))时间.

哦顺便说一句我实际上并不需要做快速排序,我只是想要一个例子来看看如何有效地使用可变数组

Answer 1

这是一个版本,只是为了证明你可以将维基百科中的代码几乎完全转换为Haskell;)

import Control.Monad.ST
import Data.Array.ST
import Data.Foldable
import Control.Monad

-- wiki-copied code starts here
partition arr left right pivotIndex = do
    pivotValue <- readArray arr pivotIndex
    swap arr pivotIndex right
    storeIndex <- foreachWith [left..right-1] left (\i storeIndex -> do
        val <- readArray arr i
        if (val <= pivotValue)
            then do
                 swap arr i storeIndex
                 return (storeIndex + 1)
            else do
                 return storeIndex )
    swap arr storeIndex right
    return storeIndex

qsort arr left right = when (right > left) $ do
    let pivotIndex = left + ((right-left) `div` 2)
    newPivot <- partition arr left right pivotIndex

    qsort arr left (newPivot - 1)
    qsort arr (newPivot + 1) right

-- wrapper to sort a list as an array
sortList xs = runST $ do
    let lastIndex = length xs - 1
    arr <- newListArray (0,lastIndex) xs :: ST s (STUArray s Int Int)
    qsort arr 0 lastIndex
    newXs <- getElems arr
    return newXs

-- test example
main = print $ sortList [212498,127,5981,2749812,74879,126,4,51,2412]

-- helpers
swap arr left right = do
    leftVal <- readArray arr left
    rightVal <- readArray arr right
    writeArray arr left rightVal
    writeArray arr right leftVal

-- foreachWith takes a list, and a value that can be modified by the function, and
-- it returns the modified value after mapping the function over the list.  
foreachWith xs v f = foldlM (flip f) v xs

Answer 2

请参阅vector-algorithms包中的'sort':http://hackage.haskell.org/packages/archive/vector-algorithms/0.4/doc/html/src/Data-Vector-Algorithms-Intro.html#sort