慢速排序算法到底有多慢

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

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

慢速排序算法到底有多慢

慢速排序

慢速排序算法在 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 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// 再排序除了最大数之外的数据

时间复杂度

通过代码与动画可以看出,慢速排序和其他排序算法效果一样,可以将一个无序数据集合进行合理排序。

但是,它的时间复杂度简直吓人!

T(n) = 2 * T(n/2) + T(n-1) + C( C 表示常量时间)

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

慢速排序算法到底有多慢

慢速排序算法到底有多慢

慢速排序算法到底有多慢


 原 创 热 文 推 荐 


毕业十年后,我忍不住出了一份程序员的高考试卷

一道腾讯面试题:厉害了我的杯

十大经典排序算法动画与解析,看我就够了!(配代码完全版)

这或许是东半球分析十大排序算法最好的一篇文章

面试官,我会写二分查找法!对,没有 bug 的那种!


慢速排序算法到底有多慢
你点的每个“在看”,我都认真当成了喜欢
本文由 程序员小吴 创作,采用 CC BY 3.0 CN协议 进行许可。 可自由转载、引用,但需署名作者且注明文章出处。如转载至微信公众号,请在先添加作者公众号二维码。
五分钟学算法 » 慢速排序算法到底有多慢

我还会在以下平台发布内容

GitHub 哔哩哔哩