1 
insertionSort :: (Ord a) => [a] -> [a]
insertionSort (x:xs) = insertionSortIter [x] xs 
    where insertionSortIter sorted []      =  sorted  
          insertionSortIter sorted (x:xs)  =  insertionSortIter (insert x sorted (length sorted)) xs
          insert x list n   --insert x in list at n
                | n == 0    = x:list
                | x < list !! (n - 1)   = insert x list (n - 1)
                | otherwise = firstns ++ (x:other) where (firstns, other) = splitAt n list
-- [1..10000] 30s                    
mergeSort :: (Ord a) => [a] -> [a]
mergeSort (x:[])      = [x]
mergeSort  list       = merge (mergeSort list1) (mergeSort list2)
        where (list1, list2) = splitAt (length list `div` 2) list
              merge [] list       = list
              merge list []       = list
              merge (x:xs) (y:ys) = if x < y then x:(merge xs (y:ys)) else y:(merge (x:xs) ys)
-- [1..10000] 2.4s

执行时间由构建时间指定（1 或 1.5 秒）。但是你仍然可以感觉到不同。

问题可能是每个分支在insert功能保护中的执行或firstns ++ (x:other)太慢。但无论如何，要将项目放在列表的末尾，我需要遍历整个列表以获得 O(n)。

4

1 回答 1

2

你的insert功能很慢。以下是如何进行插入排序：

insertionSort :: Ord a => [a] -> [a]
insertionSort xs = f [] xs
  where
    f rs []     = rs
    f rs (x:xs) = f (insert x rs) xs

    insert x []         = [x]
    insert x rrs@(r:rs) = if x < r then x:rrs else r:insert x rs

万一混淆，rrs@(r:rs)语法意味着它rrs是整个列表，r是它的头部，rs是它的尾部。

insert遍历列表并列出所有应该在前面的元素x，然后列出x后面应该在后面的元素x。

于 2013-08-18T14:06:07.190 回答