慢速排序(英語:Slowsort)是一種排序演算法。其基於合併排序的分而治之及遞迴的思想,並故意設計使排序過程非常緩慢。慢速排序由安德烈·布羅德(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)
慢速排序的運行時間關係式為 , 的漸近下限為 for any 。由於慢速排序漸近下限的時間複雜度不是多項式時間,即使在最好的情況下也比冒泡排序慢。
|
---|
| 理论 | |
---|
| 交换排序 | |
---|
| 选择排序 | |
---|
| 插入排序 | |
---|
| 归并排序 | |
---|
| 分布排序 | |
---|
| 并发排序 | |
---|
| 混合排序 | |
---|
| 其他 | |
---|
|