聊一聊那些脑洞大开、有趣又奇葩的排序算法

作者：王争，前Google工程师

微信公众号：小争哥

前段时间，网上疯传这样一个段子，”写完这个 排序 算法之后，我就被开除了“。我们一块来看看，他到底写了什么样的代码，能让主管一怒之下，把他开除了。

当我看到这段代码的时候，首先感叹的是，作者真的脑洞大开啊。不过，你还真先别嘲笑作者的智商。如果你去查一下资料的话，你就发现，这是一个经典的排序算法，叫做”睡眠排序“。哈哈，是不是很形象呢？

为了防止你写个 排序算法 被开除，又或者作为主管，一怒之下，开除员工，我今天就带你看看，历史上那些脑洞大开、有趣又奇葩的排序算法。

1. 睡眠排序算法（Sleep Sort）

我们要讲的第一个脑洞大开的排序算法，就是上面被开除的同学写的那个，睡眠排序算法。实际上，它的原理非常简单，你看代码就应该能看懂的。

如果对6个数据进行大小排序，我们创建6个线程，每个线程处理一个数字，数字对应的线程sleep的时间。比如，我们要排序{102, 338, 62, 9132, 580, 666}这样一组数据，我们就让这6个线程分别sleep 102ms、338ms、62ms、9132ms、580ms、666ms。当线程唤醒之后，最先唤醒的线程，打印出来的数据最小。以此类推，最后唤醒的线程，打印出来的数据最大。

这个排序算法，总的耗时，就是最大那个数字对应的线程sleep的时间。你可能会说，如果最大的数字很大，那等待最后一个线程睡醒，是不是要花很长时间呢？你说的没错。不过，我们可以让线程以更小的时间粒度来睡眠，比如我们把上面的睡眠时间的单位从毫秒(ms)换成微妙(us)。

而且，你可别小看这个看起来不切实际的排序算法。如果我们在未来的哪一天，真的能造出速度极快的量子计算机，那这个排序算法可能就真的切合实际了。

2. 猴子排序算法（Bogo Sort）

如果说刚刚那个排序算法还有点用的话，现在马上要讲的这个排序算法就是一个既不实用又非常低效的排序算法了。

这个排序算法的名字来自于无限猴子理论。这个理论实际上也很简单，意思就是，如果我们有无限只猴子，给他们无限的时间，让他们在键盘上随便乱敲，也可能敲出一本莎士比亚。这实际上是一个概率问题。

看明白了无限猴子理论，我们再来看下什么是猴子排序算法。猴子排序算法也很简单。它利用的也概率论知识。针对要排序的数据集合，我们每次随机生成一个排列，看是否完全满足从小到大排列，如果不满足，我们就继续再随机生成一个排列，直到随机出一个排好序的排列。总有一天会歪打正着，正好遇到一个有序的排列。

while not isInOrder(deck):
    shuffle(deck)
复制代码

3. 慢速排序算法（Slow Sort）

这个排序算法是1986年由Andrei Broder和Jorge Stolfi发表。从名字上就能看出很慢的排序算法：慢速排序算法。它从结构上，看起来有点类似归并排序算法，伪代码如下。

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) // 再排序除了最大数之外的数据
复制代码

从代码上实现上看，这个排序算法看似很牛逼的样子，分治思想、递归实现都用上了。我们想要排序下标是i到j之间的数据，算法先排序好前半段，再排序好后半段，然后把最大值放到下标为j的位置，最后还要再把除了最大值之外的下标是i到j之前的数据，再重新排序。

算法是正确，可以实现将一个无序数据集合排序的效果。但如果我们把时间复杂计算的递归公式写出来，你就知道，它的时间复杂度很高了。

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

这个时间复杂度的公式推导很复杂，我直接给出结论: ，并不是一个多项式时间复杂度的算法，也就是说，是一个无效的算法。

4. 侏儒排序算法（Stupid Sort）

Stupid排序算法，起初由 Hamid Sarbazi-Azad 于 2000 年提出，后来被 Dick Grune 命名为 “Gnome排序” 。从名字上就可以看出，它也并不是一个很高明的排序算法。这个算法是如何工作的呢？我们先看它的伪代码实现，稍后再解释。

procedure gnomeSort(a[]):
  pos := 0
  while pos < length(a):
   if (pos == 0 or a[pos] >= a[pos-1]):
     pos := pos + 1
   else:
     swap a[pos] and a[pos-1]
     pos := pos - 1
复制代码

这个算法的思想非常贴合我们平时生活中整理东西的逻辑。假设我们站在pos这个下标位置上，0到pos-1这pos个数据已经是从小到大排好序的了。如果pos-1这个位置的数据小于等于pos，那我们前进一位（pos++）；相反，如果pos-1这个位置的数据大于pos这个位置的数据，我们就将两个数交换，并且后退一步（pos--），继续跟已经排好序的数据比较。

实际上，从上面的工作原理的分析来看，这个算法有点类似冒泡排序。而且，尽管名字叫Stupid算啊，实际上，性能并不是太差，最坏情况是时间复杂度是O(n^3)。

5. 臭皮匠排序算法（Stooge Sort）

Stooge排序算法，从实现上来看，有点类似于Stupid算法。不过，它比Stupid算法的性能稍强点，时间复杂度是O(nlog 3 / log 1.5 ) = O(n2.7095...)。

Stooge排序算法是怎么工作的呢？我们先来看下它的伪代码实现。

function stoogesort(array L, i = 0, j = length(L)-1) {
  if L[i] > L[j] then
    swap L[i], L[j]
  if (j - i + 1) > 2 then
    t = (j - i + 1) / 3
    stoogesort(L, i  , j-t)
    stoogesort(L, i+t, j)
    stoogesort(L, i  , j-t)
  return L
}
复制代码

从代码实现上来看，这个算法非常规整、非常优美。我稍微解释一下。

如果最后一个元素小于第一个元素，我们交换两个数。如果当前集合元素数量大于等于3，那先递归排序前2/3的元素，再递归排序后2/3的元素，最后再递归排序一次前2/3的元素。

实现原理很巧妙哈，我们来看下，算法结束之后，是否能产生排好序的数组呢？

实际上，这个算法的正确性证明很简单。我们把整个数组分成三段，每段占1/3。前1/3段我们记作A，中间1/3段我们记作B，后面1/3段我们记作C。

经过第一轮排序之后，[AB]已经有序了，也就说，B中的数据肯定大于A中的数据。经过第二轮排序之后，[BC]就有序了，也就说C中数据肯定大于[AB]中的数据，也就是说，C中的数据肯定是这个数组中最大的1/3数据了。

那这个时候，[AB]种的数据是否仍然有序呢？经过第二轮排序之后，[AB]中的数据变得无序了，所以我们需要再进行一轮排序，也就是代码中的最后一次排序。听起来是不是有点类似汉诺塔算法呢？

今天，我只是给你展示了这些奇葩的排序算法，如果你对哪个感兴趣，可以自己去更深入的研究下。除此之外，你还知道其他哪些脑洞大开的排序算法呢？欢迎留言区说说。

关注我的微信公众号：小争哥，获取更多、更新的技术、非技术分享。

作者：前Google工程师，5万人订阅《数据结构和算法之美》专栏作者。

希望通过我加速你的技术、职场进步。