慢速排序算法到底有多慢

桃扇骨 2022-01-16 03:59 296阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

### 慢速排序 ###

慢速排序算法在 1986 年由 Andrei Broder 和 Jorge Stolfi 发表，主要采取了分治和递归的思想：

具体的操作是分为以下两大步：

1.  找出最大者
2.  将其余的数排序

其中子问题 1 又可分为以下 3 小步：

1.1 找出前 n/2 个数中的最大者

1.2 找出后 n/2 个数中的最大者

1.3 取这两个最大者中的较大者

最后，子问题 1.1 和 1.2 的解决方法是，将相应的数排序后取最后一个。

也就是说我们把原问题分解成 3 个稍微容易一点点的子问题：给前一半数排序，给后一半数排序，给除了一个数以外的其它数排序。递归地进行这一系列步骤，直到至多只剩下一个元素时，停止。

### 动画描述 ###

![640?wx\_fmt=gif][640_wx_fmt_gif]

slow sort from Timo Bingmann

国外有人对慢速排序动画写了一个段子：

**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) // 再排序除了最大数之外的数据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 表示常量时间）`

你可以通过下面三张图来理解这个时间复杂度的有多夸张！（以下图片来源于网络）

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]  
![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2]  
![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 3]

**原 创 热 文 推 荐**

☞[毕业十年后，我忍不住出了一份程序员的高考试卷][Link 1]

[☞][Link 2][一道腾讯面试题：厉害了我的杯][Link 3]

[☞][Link 4][十大经典排序算法动画与解析，看我就够了][Link 5]

[☞][Link 4][这或许是东半球分析十大排序算法最好的一篇文章][Link 6]

[☞][Link 4][面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

![640?wx\_fmt=png][640_wx_fmt_png] 你点的每个“在看”，我都认真当成了喜欢

[640_wx_fmt_jpeg]: /images/20220114/6a2621fdc18a4d309e1ab3cc89d41eef.png
[640_wx_fmt_gif]: /images/20220114/f7662524bc2b436585f504c6dade8f15.png
[640_wx_fmt_jpeg 1]: /images/20220114/aa3f11ca78b043e9a400f077830b0f26.png
[640_wx_fmt_jpeg 2]: /images/20220114/b951f618eba44407a341e0ca7008136d.png
[640_wx_fmt_jpeg 3]: /images/20220114/8fa0f590414f498aaa35c05ec9358f8c.png
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/91488249
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzA5MzY4NTQwMA==&mid=2651011536&idx=3&sn=fd5ff61a84fe2180a7c21d15acf71659&chksm=8bad8a27bcda03319570ae23d05392d287390a51ca94014422dd199450b25f43467aaaedb59e&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzA5MjcxNjc2Ng==&mid=2650560116&idx=1&sn=f9e86fa3e7b15624177b29ef1a785be4&chksm=88601dc5bf1794d30fd595d413491da189584b44fd2b2e5e40c665e58760e162616585811647&scene=21#wechat_redirect
[Link 5]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 6]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485556&idx=1&sn=344738dd74b211e091f8f3477bdf91ee&chksm=fa0e67f5cd79eee3139d4667f3b94fa9618067efc45a797b69b41105a7f313654d0e86949607&scene=21#wechat_redirect
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[640_wx_fmt_png]: /images/20220114/e193b8acb2164e3e9e6642b8b11718e1.png