相关疑难解决方法(0)

我知道quicksort的O(n log n)平均时间复杂度.伪快速排序(当你从足够远的地方看它,具有适当高的抽象级别时只是一个快速排序),通常用于演示函数语言的简洁性如下(在Haskell中给出):

quicksort :: Ord a => [a] -> [a]
quicksort []     = []
quicksort (p:xs) = quicksort [y | y<-xs, y<p] ++ [p] ++ quicksort [y | y<-xs, y>=p]

好的,所以我知道这件事有问题.最大的问题是它没有排序,这通常是quicksort的一大优势.即使这没关系,它仍然需要比典型的快速排序更长的时间,因为它在分区时必须进行两次列表传递,然后它会进行昂贵的附加操作以将其拼接回来.此外,选择第一个元素作为枢轴不是最佳选择.

但即便考虑所有这些,这个快速排序的平均时间复杂度与标准快速排序不同吗？即,O(n log n)？因为追加和分区仍然具有线性时间复杂度,即使它们效率低下.

在Haskell，差异表中的感

[a]使用有效的串联操作表示列表

似乎是在功能组成上实现的。

但是，功能和（动态）功能组合也必须使用数据结构以某种方式在计算机的内存中表示，这提出了一个问题，即在不使用功能组合的情况下如何在Haskell中实现dlist，而是通过一些基本的纯功能实现基于节点的数据结构。如何实现与功能组合相同的性能保证？

我必须将给定列表拆分为非空子列表,每个子列表按严格升序排列,严格按降序排列,或包含所有相等的元素.例如,[5,6,7,2,1,1,1]应该成为[[5,6,7],[2,1],[1,1]].

这是我到目前为止所做的:

splitSort :: Ord a => [a] -> [[a]] 
splitSort ns = foldr k [] ns
  where
    k a []  = [[a]]
    k a ns'@(y:ys) | a <= head y = (a:y):ys
                   | otherwise = [a]:ns'

我认为我非常接近但是当我使用它时输出[[5,6,7],[2],[1,1,1]而不是[[5,6,7],[2,1] ,[1,1].