慢速排序算法到底有多慢

来自:五分钟学算法(微信号:blgczzz),作者:程序员小吴


慢速排序

慢速排序算法在 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 表示常量时间)

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



推荐↓↓↓
算法与数据结构
上一篇:数据结构与算法——单链表 下一篇:算法数据结构中有哪些奇技淫巧?