缓慢插入排序

Question

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.5s)一起指定。但你还是能感受到不同。

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

Answer 1

您的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后面的元素。