慢速排序

慢速排序是一种排序算法。其基于合并排序的分而治之及递回的思想,并故意设计使排序过程非常缓慢。慢速排序由Andrei Broder及Jorge Stolfi在1986年发表的论文Pessimal Algorithms and Simplexity Analysis[1](论文名称是渐进最优算法及计算复杂性理论的戏仿)中提出。

算法

慢速排序是一种原地算法的递回算法。

在简单的虚拟码中,此算法可以被表示为:

procedure slowsort(A, i, j)                           // 排序一個整數或浮點數數列 A[i],...,A[j] ,若要使用其他的資料類型則必須重載大於或小於運算符
    if i ≥ j then
        return
    m := ⌊(i+j) / 2⌋                            
    slowsort(A, i, m)                                 // (1.1)
    slowsort(A, m+1, j)                               // (1.2)
    if A[j] < A[m] then
        swap A[j] and A[m]                            // (1.3)
    slowsort(A, i, j-1)                               // (2)
  • 慢速排序法排序前半部的元素(1.1)
  • 以慢速排序法排序后半部的元素(1.2)
  • 比较1.1及1.2排序结果的最后一个元素,选择相对较大的元素放到列表尾端(1.3)
  • 排除1.3的元素后,将列表剩下的元素以慢速排序法排序(2)

以 Haskell(纯函式编程语言)的实现如下:

slowsort :: Ord a => [a] -> [a]
slowsort xs
  | length xs <= 1 = xs
  | otherwise      = slowsort xsnew ++ [max llast rlast]  -- (2)
    where  
      l     = slowsort $ take m xs  -- (1.1)
      r     = slowsort $ drop m xs  -- (1.2)
      llast = last l
      rlast = last r
      xsnew = init l ++ min llast rlast : init r
      m     = fst (divMod (length xs) 2)

复杂度

慢速排序的运行时间关系式为 {\displaystyle T(n)=2T(n/2)+T(n-1)+1}{\displaystyle T(n)}的渐近下限为 {\displaystyle \Omega \left(n^{\frac {\log _{2}(n)}{(2+\epsilon )}}\right)} for any {\displaystyle \epsilon >0}。由于慢速排序渐近下限的时间复杂度不是多项式时间,即使在最好的情况下也比泡沫排序慢。

原文地址:https://zh.wikipedia.org/wiki/%E6%85%A2%E9%80%9F%E6%8E%92%E5%BA%8F

知识共享 署名-相同方式共享 3.0协议之条款下提供

文章作者: 张拓
文章链接: http://www.xssl.online/%e6%85%a2%e9%80%9f%e6%8e%92%e5%ba%8f/
版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 4.0 许可协议。转载请注明来自 张拓的博客
浏览次数: 512

张拓

陕西西安蓝田张拓QQ1070410059。一生所求不过“心安”二字。 然,尘世多纷扰。

发表回复