緩慢插入排序

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）的整個列表。

來源

2013-08-18 vlastachu

這是什麼問題？ –

'insertionSortIter'遍歷O（n）個位置，並在每次迭代中調用O（n）時間的'!!'運算符，使得它僅僅插入一個單獨的項目（O ^^）。不要這樣做。 –

ДМИТРИЙ，很高興在那裏見到你。爲什麼這麼慢。我究竟做錯了什麼。 – vlastachu

你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 [email protected](r:rs) = if x < r then x:rrs else r:insert x rs

在混亂的情況下，[email protected](r:rs)語法意味着rrs是整個列表，r是它的頭，rs是它的尾巴。

insert經過列表，並拿出所有的都應該是在x前面的元素，那麼它提出了x後跟應該是x後的元素。

來源

2013-08-18 14:06:07 Olathe

不錯，謝謝！在最佳情況下，原始插入排序O（n）。所以最糟糕的情況是O（n），我們似乎沒有辦法做到這一點。 – vlastachu

您可以使用foldr而不是f。 – augustss

所以最終的代碼是'insertionSort（x：xs）= foldr insert [x] xs'。非常好。出於某種原因，我認爲我們無法在foldr中獲得列表。很高興這種刻板印象被打破了。嗯，但與foldr排序工程非線性較慢。 – vlastachu

緩慢插入排序

回答

相關問題