原文鏈接

慢速排序

慢速排序算法在 1986 年由 Andrei Broder 和 Jorge Stolfi 發表，主要採取了分治和遞歸的思想：

• 將問題變成若干個子問題，每一個子問題都僅僅稍微比原問題簡單一點；
• 再遞歸地把每一個子問題變成若干子子問題，如此儘可能多地增加子問題的數量；
• 直到子問題無法劃分為止

具體的操作是分為以下兩大步：

1. 找出最大者
2. 將其餘的數排序

其中子問題 1 又可分為以下 3 小步：

1.1 找出前 n/2 個數中的最大者

1.2 找出後 n/2 個數中的最大者

1.3 取這兩個最大者中的較大者

最後，子問題 1.1 和 1.2 的解決方法是，將相應的數排序後取最後一個。

也就是說我們把原問題分解成 3 個稍微容易一點點的子問題：給前一半數排序，給後一半數排序，給除了一個數以外的其它數排序。遞歸地進行這一系列步驟，直到至多只剩下一個元素時，停止。

動畫描述

國外有人對慢速排序動畫寫了一個段子：

slow sort is just merge sort with the severe paranoia that the elements have moved themselves while it wasn’t looking.

排序的元素趁大家不注意的時候偷偷的移動一下。

代碼實現

procedure slowsort(A,i,j)
  if i >= j then return
    m = (i + j) / 2                           
    slowsort(A,i,m) // 先排序前半段
    slowsort(A,m + 1,j) // 再排序後半段
  if A[j] < A[m] then swap A[j] and A[m] // 找到最大數，放到末尾
    slowsort(A,i,j - 1) // 再排序除了最大數之外的數據

時間複雜度

通過代碼與動畫可以看出，慢速排序和其他排序算法效果一樣，可以將一個無序數據集合進行合理排序。

但是，它的時間複雜度簡直嚇人！

T(n) = 2 * T(n/2) + T(n-1) + C（ C 表示常量時間）

你可以通過下面三張圖來理解這個時間複雜度的有多誇張！（以下圖片來源於網絡）

來源 | 五分鐘學算法
作者 | 程序員小吳