Haskell合并排序
示例
有序合并两个有序列表
保留重复项：
merge :: Ord a => [a] -> [a] -> [a]
merge xs [] = xs
merge [] ys = ys
merge (x:xs) (y:ys) | x <= y = x:merge xs (y:ys)
| otherwise = y:merge (x:xs) ys自顶向下版本：
msort :: Ord a => [a] -> [a]
msort [] = []
msort [a] = [a]
msort xs = merge (msort (firstHalf xs)) (msort (secondHalf xs))
firstHalf xs = let { n = length xs } in take (div n 2) xs
secondHalf xs = let { n = length xs } in drop (div n 2) xs定义这种方式是为了清楚而非效率。
使用示例：
> msort [3,1,4,5,2]
结果：
[1,2,3,4,5]
自下而上的版本：
msort [] = []
msort xs = go [[x] | x <- xs]
where
go [a] = a
go xs = go (pairs xs)
pairs (a:b:t) = merge a b : pairs t
pairs t = t
热门推荐
10 情侣祝福语古文简短独特
11 酒店伴娘祝福语简短
12 晚上甜蜜的祝福语简短
13 给新娘简短的祝福语
14 当爸爸的简短祝福语
15 洛宁新年祝福语大全简短
16 新年祝福语简短搞笑幽默
17 结婚祝福语大全简短霸气
18 新人结婚祝福语简短高端