慢速排序慢速排序(英語: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)
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 。由於慢速排序漸近下限的時間複雜度不是多項式時間,即使在最好的情況下也比冒泡排序慢。 參考資料
|