另一方面，可以在 Haskell 中使用向量来实现就地快速排序。
第二个算法比第一个快多少？
当然，这取决于实施。如下所示，对于不太短的列表，对可变向量或数组进行适当的就地排序比排序列表快得多，即使包括从列表到列表的转换时间（并且该转换弥补了大部分时间）。
但是，列表算法会产生增量输出，而数组/向量算法在完成之前不会产生任何结果，因此排序列表仍然是可取的。
我不确切知道链接的可变数组/向量算法做错了什么。但他们做错了事。
对于可变向量代码，它似乎使用了盒装向量，并且是多态的，两者都会对性能产生重大影响，尽管如果函数是{-# INLINABLE #-}.
对于IOUArray代码，好吧，它看起来很有趣，但速度很慢。它使用IORef,readArray和writeArray并没有明显的严格性。那么，它所花费的糟糕时间就不足为奇了。
使用, 对（单态）C 代码进行更直接的翻译STUArray，并使用包装器使其在列表中工作¹，
{-# LANGUAGE BangPatterns #-}
module STUQuickSort (stuquick) where
import Data.Array.Base (unsafeRead, unsafeWrite)
import Data.Array.ST
import Control.Monad.ST
stuquick :: [Int] -> [Int]
stuquick [] = []
stuquick xs = runST (do
let !len = length xs
arr <- newListArray (0,len-1) xs
myqsort arr 0 (len-1)
-- Can't use getElems for large arrays, that overflows the stack, wth?
let pick acc i
| i < 0 = return acc
| otherwise = do
!v <- unsafeRead arr i
pick (v:acc) (i-1)
pick [] (len-1))
myqsort :: STUArray s Int Int -> Int -> Int -> ST s ()
myqsort a lo hi
| lo < hi = do
let lscan p h i
| i < h = do
v <- unsafeRead a i
if p < v then return i else lscan p h (i+1)
| otherwise = return i
rscan p l i
| l < i = do
v <- unsafeRead a i
if v < p then return i else rscan p l (i-1)
| otherwise = return i
swap i j = do
v <- unsafeRead a i
unsafeRead a j >>= unsafeWrite a i
unsafeWrite a j v
sloop p l h
| l < h = do
l1 <- lscan p h l
h1 <- rscan p l1 h
if (l1 < h1) then (swap l1 h1 >> sloop p l1 h1) else return l1
| otherwise = return l
piv <- unsafeRead a hi
i <- sloop piv lo hi
swap i hi
myqsort a lo (i-1)
myqsort a (i+1) hi
| otherwise = return ()
以及对未装箱向量的良好排序（Introsort，而不是快速排序）的包装器，
module VSort where
import Data.Vector.Algorithms.Intro
import qualified Data.Vector.Unboxed as U
import Control.Monad.ST
vsort :: [Int] -> [Int]
vsort xs = runST (do
v <- U.unsafeThaw $ U.fromList xs
sort v
s <- U.unsafeFreeze v
return $ U.toList s)
我得到的时间更符合预期（注意：对于这些时间，在调用排序算法之前已经deepseq编辑了随机列表。没有它，转换为 anSTUArray会慢得多，因为它会首先评估一长串 thunk确定长度。vectorfromList包的转换不存在这个问题。将 移到转换为，其他排序[和转换，在vector情况下]算法花费的时间要少一点，所以vector之间的区别-algorithms的 introsort 和快速排序变得更大一些。）：deepseqSTUArraySTUArray
list size: 200000 -O2 -fllvm -fllvm-O2
──────── ──────── ──────── ──────── ────────
Data.List.sort 0.663501s 0.665482s 0.652461s 0.792005s
Naive.quicksort 0.587091s 0.577796s 0.585754s 0.667573s
STUArray.quicksort 1.58023s 0.142626s 1.597479s 0.156411s
VSort.vsort 0.820639s 0.139967s 0.888566s 0.143918s
没有优化的时代对STUArray. unsafeRead并且unsafeWrite必须内联才能快速。如果没有内联，您将获得每次调用的字典查找。因此对于大型数据集，我省略了未优化的方法：
list size: 3000000 -O2 -fllvm-O2
──────── ──────── ────────
Data.List.sort 16.728576s 16.442377s
Naive.quicksort 14.297534s 12.253071s
STUArray.quicksort 2.307203s 2.200807s
VSort.vsort 2.069749s 1.921943s
您可以看到，如果操作正确，对可变未装箱数组进行就地排序比基于列表的排序要快得多。排序和未装箱可变向量上的排序之间的差异STUArray是由于算法不同还是这里的向量确实更快，我不知道。由于我从未观察到向量比STUArrays 更快²，我倾向于相信前者。STUArray快速排序和 introsort
之间的区别部分是由于矢量包提供的更好的列表之间的转换，部分原因是不同的算法。
在Louis Wasserman的建议下，我使用矢量算法包中的其他排序算法运行了一个快速基准测试，并使用了一个不太大的数据集。结果并不令人惊讶，良好的通用算法 heapsort、introsort 和 mergesort 都做得很好，时间接近未装箱可变数组上的快速排序（但当然，快速排序在几乎排序的输入上会降级为二次行为，而这些保证 O(n*log n) 最坏情况）。专用排序算法AmericanFlag和基数排序做得不好，因为输入不适合他们的目的（基数排序在较大范围的较大输入上会做得更好，因为它比数据所需的传递次数要多得多）。由于其二次行为，插入排序是迄今为止最糟糕的。
AmericanFlag:
list size: 300000 -O2 -fllvm-O2
──────── ──────── ────────
Data.List.sort 1.083845s 1.084699s
Naive.quicksort 0.981276s 1.05532s
STUArray.quicksort 0.218407s 0.215564s
VSort.vsort 2.566838s 2.618817s
Heap:
list size: 300000 -O2 -fllvm-O2
──────── ──────── ────────
Data.List.sort 1.084252s 1.07894s
Naive.quicksort 0.915984s 0.887354s
STUArray.quicksort 0.219786s 0.225748s
VSort.vsort 0.213507s 0.20152s
Insertion:
list size: 300000 -O2 -fllvm-O2
──────── ──────── ────────
Data.List.sort 1.168837s 1.066058s
Naive.quicksort 1.081806s 0.879439s
STUArray.quicksort 0.241958s 0.209631s
VSort.vsort 36.21295s 27.564993s
Intro:
list size: 300000 -O2 -fllvm-O2
──────── ──────── ────────
Data.List.sort 1.09189s 1.112415s
Naive.quicksort 0.891161s 0.989799s
STUArray.quicksort 0.236596s 0.227348s
VSort.vsort 0.221742s 0.20815s
Merge:
list size: 300000 -O2 -fllvm-O2
──────── ──────── ────────
Data.List.sort 1.087929s 1.074926s
Naive.quicksort 0.875477s 1.019984s
STUArray.quicksort 0.215551s 0.221301s
VSort.vsort 0.236661s 0.230287s
Radix:
list size: 300000 -O2 -fllvm-O2
──────── ──────── ────────
Data.List.sort 1.085658s 1.085726s
Naive.quicksort 1.002067s 0.900985s
STUArray.quicksort 0.217371s 0.228973s
VSort.vsort 1.958216s 1.970619s
结论：除非您有特定的理由不这样做，否则推荐使用vector-algorithms中的一种良好的通用排序算法，以及在必要时从列表转换为列表的包装器，这是对大型列表进行排序的推荐方法。（这些算法也适用于盒装向量，在我的测量中比未盒装的向量慢大约 50%。）对于短列表，转换的开销会很大，以至于它不会支付。
现在，在@applicative 的建议下，看看vector-algorithms ' introsort 的排序时间，对未装箱向量的快速排序和改进的（无耻地窃取实现unstablePartition）快速排序STUArray。
改进的STUArray快速排序：
{-# LANGUAGE BangPatterns #-}
module NQuick (stuqsort) where
import Data.Array.Base (unsafeRead, unsafeWrite, getNumElements)
import Data.Array.ST
import Control.Monad.ST
import Control.Monad (when)
stuqsort :: STUArray s Int Int -> ST s ()
stuqsort arr = do
n <- getNumElements arr
when (n > 1) (myqsort arr 0 (n-1))
myqsort :: STUArray s Int Int -> Int -> Int -> ST s ()
myqsort a lo hi = do
p <- unsafeRead a hi
j <- unstablePartition (< p) lo hi a
h <- unsafeRead a j
unsafeWrite a j p
unsafeWrite a hi h
when (j > lo+1) (myqsort a lo (j-1))
when (j+1 < hi) (myqsort a (j+1) hi)
unstablePartition :: (Int -> Bool) -> Int -> Int -> STUArray s Int Int -> ST s Int
{-# INLINE unstablePartition #-}
unstablePartition f !lf !rg !v = from_left lf rg
where
from_left i j
| i == j = return i
| otherwise = do
x <- unsafeRead v i
if f x
then from_left (i+1) j
else from_right i (j-1)
from_right i j
| i == j = return i
| otherwise = do
x <- unsafeRead v j
if f x
then do
y <- unsafeRead v i
unsafeWrite v i x
unsafeWrite v j y
from_left (i+1) j
else from_right i (j-1)
向量快速排序：
module VectorQuick (vquicksort) where
import qualified Data.Vector.Unboxed.Mutable as UM
import qualified Data.Vector.Generic.Mutable as GM
import Control.Monad.ST
import Control.Monad (when)
vquicksort :: UM.STVector s Int -> ST s ()
vquicksort uv = do
let li = UM.length uv - 1
ui = UM.unsafeSlice 0 li uv
p <- UM.unsafeRead uv li
j <- GM.unstablePartition (< p) ui
h <- UM.unsafeRead uv j
UM.unsafeWrite uv j p
UM.unsafeWrite uv li h
when (j > 1) (vquicksort (UM.unsafeSlice 0 j uv))
when (j + 1 < li) (vquicksort (UM.unsafeSlice (j+1) (li-j) uv))
计时码：
{-# LANGUAGE BangPatterns #-}
module Main (main) where
import System.Environment (getArgs)
import System.CPUTime
import System.Random
import Text.Printf
import Data.Array.Unboxed
import Data.Array.ST hiding (unsafeThaw)
import Data.Array.Unsafe (unsafeThaw)
import Data.Array.Base (unsafeAt, unsafeNewArray_, unsafeWrite)
import Control.Monad.ST
import Control.Monad
import qualified Data.Vector.Unboxed as U
import qualified Data.Vector.Unboxed.Mutable as UM
import NQuick
import VectorQuick
import qualified Data.Vector.Algorithms.Intro as I
nextR :: StdGen -> (Int, StdGen)
nextR = randomR (minBound, maxBound)
buildArray :: StdGen -> Int -> UArray Int Int
buildArray sg size = runSTUArray (do
arr <- unsafeNewArray_ (0, size-1)
let fill i g
| i < size = do
let (r, g') = nextR g
unsafeWrite arr i r
fill (i+1) g'
| otherwise = return arr
fill 0 sg)
buildVector :: StdGen -> Int -> U.Vector Int
buildVector sg size = U.fromList $ take size (randoms sg)
time :: IO a -> IO ()
time action = do
t0 <- getCPUTime
action
t1 <- getCPUTime
let tm :: Double
tm = fromInteger (t1 - t0) * 1e-9
printf "%.3f ms\n" tm
stu :: UArray Int Int -> Int -> IO ()
stu ua sz = do
let !sa = runSTUArray (do
st <- unsafeThaw ua
stuqsort st
return st)
forM_ [0, sz `quot` 2, sz-1] (print . (sa `unsafeAt`))
intro :: U.Vector Int -> Int -> IO ()
intro uv sz = do
let !sv = runST (do
st <- U.unsafeThaw uv
I.sort st
U.unsafeFreeze st)
forM_ [0, sz `quot` 2, sz-1] (print . U.unsafeIndex sv)
vquick :: U.Vector Int -> Int -> IO ()
vquick uv sz = do
let !sv = runST (do
st <- U.unsafeThaw uv
vquicksort st
U.unsafeFreeze st)
forM_ [0, sz `quot` 2, sz-1] (print . U.unsafeIndex sv)
main :: IO ()
main = do
args <- getArgs
let !num = case args of
(a:_) -> read a
_ -> 1000000
!sg <- getStdGen
let !ar = buildArray sg num
!vc = buildVector sg num
!v2 = buildVector sg (foo num)
algos = [ ("Intro", intro v2), ("STUArray", stu ar), ("Vquick", vquick vc) ]
printf "Created data to be sorted, last elements %d %d %d\n" (ar ! (num-1)) (vc U.! (num-1)) (v2 U.! (num-1))
forM_ algos $ \(name, act) -> do
putStrLn name
time (act num)
-- For the prevention of sharing
foo :: Int -> Int
foo n
| n < 0 = -n
| n > 0 = n
| otherwise = 3
结果（仅次）：
$ ./timeSorts 3000000
Intro
587.911 ms
STUArray
402.939 ms
Vquick
414.936 ms
$ ./timeSorts 1000000
Intro
193.970 ms
STUArray
131.980 ms
Vquick
134.979 ms
STUArray正如预期的那样，在和未装箱的向量上几乎相同的快速排序几乎花费了相同的时间。（旧的快速排序实现比 introsort 慢约 15%。与上述时间相比，大约 70-75% 用于从列表转换到列表。）
在随机输入上，快速排序的性能明显优于 introsort，但在几乎排序的输入上，它们的性能会下降，而 introsort 不会。
¹ 用 s 使代码多态STUArray充其量是一件痛苦的事，用IOUArrays 做这件事并让排序和包装器{-# INLINABLE #-}在优化的情况下产生相同的性能 - 如果没有，多态代码会明显变慢。
² 使用相同的算法，当我比较时（不经常），两者在测量精度范围内总是同样快。