查看“︁慢速排序”︁的源代码

{{for|其他"慢速排序"|Bogo排序}}
'''慢速排序'''（{{lang-en|Slowsort}}）是一種[[排序演算法]]。其基於[[合併排序]]的分而治之及遞迴的思想，並故意設計使排序過程非常緩慢。慢速排序由安德烈·布羅德（Andrei Broder）及豪爾赫·斯托爾菲（Jorge Stolfi）在1986年發表的論文《Pessimal Algorithms and Simplexity Analysis》<ref>{{cite journal |title=Pessimal Algorithms and Simplexity Analysis |date=1984 |author1=Andrei Broder |author2=Jorge Stolfi |journal=ACM SIGACT NEWS, 16(3):49-53, 1984 |url=http://www.mipmip.org/tidbits/pasa.pdf |doi=10.1145/990534.990536 |access-date=2021-06-19 |archive-date=2021-10-01 |archive-url=https://web.archive.org/web/20211001011211/https://www.mipmip.org/tidbits/pasa.pdf |dead-url=no }}</ref>（論文名稱是[[漸進最優|漸進最優算法]]及[[計算複雜性理論]]的[[戲仿]]）中提出。

==演算法==
慢速排序是一種[[原地算法]]的[[遞迴|递归算法]]。

在简单的[[虛擬碼|伪代码]]中，此演算法可以被表示为：

 '''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]]（純[[函数式编程|函式程式語言]]）的實現如下：
<syntaxhighlight lang="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)
</syntaxhighlight>

==複雜度==
慢速排序的運行時間關係式為 <math> T(n) = 2 T(n/2) + T(n-1) + 1 </math>，
<math> T(n) </math>的[[大Ω符號|漸近下限]]為
<math>\Omega\left(n^{ \frac{\log_2(n)}{(2+\epsilon)}}\right)</math> for any <math> \epsilon > 0 </math>。由於慢速排序漸近下限的時間複雜度不是[[多項式時間]]，即使在最好的情況下也比[[泡沫排序|冒泡排序]]慢。

== 參考資料 ==
{{Reflist}}
{{排序算法表}}
{{算法}}

[[Category:排序算法]]
[[Category:1961年科學]]
[[Category:1961年科學]]