15

我知道快速排序具有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]

好的，所以我知道这件事有问题。这样做的最大问题是它没有就地排序，这通常是快速排序的一大优势。即使这无关紧要，它仍然会比典型的快速排序花费更长的时间，因为它在对列表进行分区时必须执行两次遍历，并且它会执行昂贵的附加操作以在之后将其拼接在一起。此外，选择第一个元素作为枢轴不是最佳选择。

但即使考虑到所有这些，这种快速排序的平均时间复杂度是否与标准快速排序相同？即，O(n log n)? 因为追加和分区仍然具有线性时间复杂度，即使它们效率低下。

4

6 回答 6

9

这种“快速排序”实际上是砍伐森林的树排序： http ://www.reddit.com/r/programming/comments/2h0j2/real_quicksort_in_haskell

data Tree a = Leaf | Node a (Tree a) (Tree a)

mkTree [] = Leaf
mkTree (x:xs) = Node x (mkTree (filter (<= x) xs)) (mkTree (filter (x <) xs))

二叉树是不平衡的，因此构建搜索树的最坏情况复杂度为 O(N^2)，平均情况复杂度为 O(N*Log N)。

foldTree f g Leaf = g
foldTree f g (Node x l r) = f x (foldTree f g l) (foldTree f g r)

treeSort l = foldTree (\x lft rht -> lft++[x]++rht) [] (mkTree l)

检索算法具有 O(N^2) 最坏情况和 O(N*Log N) 平均情况复杂度。

均衡：

Prelude> let rnds = iterate step where step x = (75*x) `mod` 65537
Prelude> length . quicksort . take 4000 . rnds $ 1
4000
(0.08 secs, 10859016 bytes)
Prelude> length . quicksort . take 8000 . rnds $ 1
8000
(0.12 secs, 21183208 bytes)
Prelude> length . quicksort . take 16000 . rnds $ 1
16000
(0.25 secs, 42322744 bytes)

不太平衡：

Prelude> length . quicksort . map (`mod` 10) $ [1..4000]
4000
(0.62 secs, 65024528 bytes)
Prelude> length . quicksort . map (`mod` 10) $ [1..8000]
8000
(2.45 secs, 241906856 bytes)
Prelude> length . quicksort . map (`mod` 10) $ [1..16000]
16000
(9.52 secs, 941667704 bytes)
于 2012-07-06T07:08:15.890 回答
5

我同意你的假设，即平均时间复杂度仍然是O(n log n). 我不是专家，100% 肯定，但这些是我的想法：

这是就地快速排序的伪代码：（使用 l=1 和 r=数组长度调用快速排序）

Quicksort(l,r)  
--------------
IF r-l>=1 THEN  
    choose pivot element x of {x_l,x_l+1,...,x_r-1,x_r}   
    order the array-segment x_l,...x_r in such a way that  
        all elements < x are on the left side of x // line 6  
        all elements > x are on the right side of x // line 7  
    let m be the position of x in the 'sorted' array (as said in the two lines above)  
    Quicksort(l,m-1);  
    Quicksort(m+1,r)  
FI

然后，平均时间复杂度分析通过选择第 6 行和第 7 行中的“<”-比较作为该算法中的主要操作进行推理，最终得出平均时间复杂度为 O(n log n) 的结论。由于没有考虑“以这样的方式对数组段 x_l、...x_r 进行排序”的成本（如果你想找到界限，只有主导操作在时间复杂度分析中很重要），我认为“因为它在对它进行分区时必须执行两次列表传递”不是问题，因为您的 Haskell 版本在此步骤中只需要大约两倍的时间。附录操作也是如此，我同意这不会增加渐近成本：

因为追加和分区仍然具有线性时间复杂度，即使它们效率低下。

为了方便起见，我们假设这将“n”加到我们的时间复杂度成本中，因此我们有“O(n log n+n)”。由于存在一个自然数 o，对于所有大于 o 的自然数，n log n > n 都成立，因此您可以估计 n log n +n 到顶部 2 n log n 和底部 n log n，因此n log n+n = O(n log n)。

此外，选择第一个元素作为枢轴不是最佳选择。

我认为枢轴元素的选择在这里无关紧要，因为在平均案例分析中，您假设数组中元素的均匀分布。您不知道应该从数组中的哪个位置选择它，因此您必须考虑所有这些情况，在这些情况下，您的枢轴元素（独立于您取它的列表的哪个位置）是第 i-st 最小元素在您的列表中，对于 i=1...r。

于 2012-07-06T07:25:47.257 回答
4

我可以在Ideone.com上为您提供一个运行时测试，它似乎显示了基于 (++) 的版本和使用Landei 答案中的累加器技术的版本以及另一个使用了一个的版本或多或少的线性运行时间-通过三路分区。在有序数据上，这对所有这些数据都变成二次方或更糟。

-- random:   100k        200k         400k         800k
-- _O    0.35s-11MB  0.85s-29MB   1.80s-53MB   3.71s-87MB   n^1.3  1.1  1.0
-- _P    0.36s-12MB  0.80s-20MB   1.66s-45MB   3.76s-67MB   n^1.2  1.1  1.2
-- _A    0.31s-14MB  0.62s-20MB   1.58s-54MB   3.22s-95MB   n^1.0  1.3  1.0
-- _3    0.20s- 9MB  0.41s-14MB   0.88s-24MB   1.92s-49MB   n^1.0  1.1  1.1

-- ordered:   230     460     900     1800
-- _P        0.09s   0.33s   1.43s    6.89s                 n^1.9  2.1  2.3
-- _A        0.09s   0.33s   1.44s    6.90s                 n^1.9  2.1  2.3
-- _3        0.05s   0.15s   0.63s    3.14s                 n^1.6  2.1  2.3

quicksortO xs = go xs  where
  go []  =  []
  go (x:xs) = go [y | y<-xs, y<x] ++ [x] ++ go [y | y<-xs, y>=x]

quicksortP xs = go xs  where
  go []  =  []
  go (x:xs) = go [y | y<-xs, y<x] ++ (x : go [y | y<-xs, y>=x])

quicksortA xs = go xs [] where
  go [] acc = acc
  go (x:xs) acc = go [y | y<-xs, y<x] (x : go [y | y<-xs, y>=x] acc)

quicksort3 xs = go xs [] where
  go     (x:xs) zs = part x xs zs [] [] []
  go     []     zs = zs
  part x []     zs a b c = go a ((x : b) ++ go c zs)
  part x (y:ys) zs a b c =
      case compare y x of
                  LT -> part x ys zs (y:a) b c
                  EQ -> part x ys zs a (y:b) c
                  GT -> part x ys zs a b (y:c)

经验运行时复杂度在这里被估计为O(n^a)where a = log( t2/t1 ) / log( n2/n1 )。时间非常近似，因为 ideone 对于偶尔的离群值不是很可靠，但是对于检查时间复杂度来说就足够了。

因此，这些数据似乎表明，单通道分区比两通道方案快 1.5 倍至 2 倍，并且使用(++)绝不会减慢速度 - 根本没有。即“追加操作”根本不是“昂贵的”。二次行为或 (++)/append 似乎是一个城市神话——当然在 Haskell 上下文中（编辑： ...即在保护递归/尾递归模 cons的上下文中；参见这个答案）（更新：如用户：AndrewC 解释说，左折叠确实是二次的；右(++)折叠使用时是线性的；更多关于这个这里和这里）。

稍后补充：为了稳定，三向分区快速排序版本也应该以自上而下的方式构建其部分：

q3s xs = go xs [] where
  go     (x:xs) z = part x xs  go  (x:)  (`go` z)
  go     []     z = z
  part x []      a  b  c = a [] (b (c []))
  part x (y:ys)  a  b  c =
      case compare y x of
                  LT -> part x ys  (a . (y:))  b  c
                  EQ -> part x ys  a  (b . (y:))  c
                  GT -> part x ys  a  b  (c . (y:))

（性能未测试）。

于 2012-07-07T08:36:22.567 回答
2

我不知道这在多大程度上提高了运行时的复杂性，但是通过使用累加器可以避免昂贵的(++)：

quicksort xs = go xs [] where
  go [] acc = acc
  go (x:xs) acc = go [y | y<-xs, y<x] (x : go [y | y<-xs, y>=x] acc)
于 2012-07-06T10:15:25.323 回答
0

是的，这个版本具有与经典版本相同的渐近partition复杂性——您将线性时间替换为：两次通过（<和>=），并且您拥有额外的线性时间++（包括线性重新分配/复制）。所以它是一个比就地分区更糟糕的常数因子，但它仍然是线性的。该算法的所有其他方面都是相同的，因此给出“真实”（即就地）快速排序的 O(n log n) 平均情况的相同分析在这里仍然成立。

于 2012-09-03T21:07:01.613 回答
0

在此处查找适用于数组和列表的真正 O(n log n) 快速排序： http : //citeseer.ist.psu.edu/viewdoc/download ?doi=10.1.1.23.4398&rep=rep1&type=pdf在 Common Lisp 中很容易实现，并且它优于许多商业 lisp 的排序实现。

于 2012-09-02T20:09:52.557 回答