使用一系列反转对数组进行排序的最有效方法是什么？

Question

我有一个已经按降序排序的整数列表，但是一个函数获取第一个元素的值（我们称之为 x）并将 subtract 1 映射到x 应用列表其余部分（不包括第一个元素）的值。（我正在尝试实现递归算法来检查 a graphic sequence。）

list1 = [4,4,3,2,2,2,2,1] --an example of a nonincreasing list
newList = (/s -> map (subtract 1) (fst s) ++ snd s) $ splitAt (head list1) (tail list1)
                       --newList == [3,2,1,1,2,2,1]
--only these four need to be swapped     | | | |             
sortedList = sortFunction newList --[3,2,2,2,1,1,1]

新的列表需要重新降序排列，以便进行下一步的递归。我试过使用 Data.List.sort，但是对于大型列表来说这变得相当慢，因为它应用于每个递归级别。

将 subtract 1 映射到非递增整数列表开头的性质意味着实际上只有一个位置存在反转：例如，在前面的代码中，前两个 1只需要与后面的两个2交换，以便对列表进行排序。

执行此排序最有效（即最快）的方法是什么？另外，对于这项工作，是否有更有效的数据结构可以代替列表？

Answer 1

您最好进行运行长度编码。这样您就不必为了保持列表排序而挖得太远。

（警告：未经测试的 Haskell 代码。）函数

rlEncode xs = [(length xs', head xs') | xs' <- reverse $ group $ sort xs]

将[4,4,3,2,2,2,2,1]变为[(2,4),(1,3),(4,2),(1,1)]。那么我们可以写一个"constructor"

rlCons (n, x) [] = [(n, x)]
rlCons (n, x) rle@((n', x') : rle')
    | x == x' = (n + n', x) : rle'
    | otherwise = (n, x) : rle

和一个"destructor"

rlUncons [] = Nothing
rlUncons ((1, x) : rle) = Just (x, rle)
rlUncons ((n, x) : rle) = Just (x, (n - 1, x) : rle)

用于运行长度的编码列表。然后 isGraphic，以其最简单且效率最低的形式，看起来像这样。

isGraphic [] = True
isGraphic rle = fromMaybe False $ do
    (d, rle') <- rlUncons rle
    rle'' <- deflate d rle'
    return $ isGraphic rle''

deflate 0 rle = Just rle
deflate _d [] = Nothing
deflate _d [(_,0)] = Nothing
deflate d ((n, d') : rle)
    | d < n = Just $ rlCons (n - d, d') $ rlCons (d, d' - 1) rle
    | otherwise = liftM (rlCons (n, d' - 1)) $ deflate (d - n) rle

使用一系列反转对数组进行排序的最有效方法是什么？

What's the most efficient way to sort an array with a single series of inversions?

sorting

algorithm

recursion

haskell

graph-algorithm