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

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)]。然后我们可以写一个“构造函数”

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

和一个“析构函数”

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