那些让人笑出声的Meme排序算法

学算法的时候，老师教给我们的都是正经算法：冒泡排序、快速排序、归并排序……它们勤勤恳恳，复杂度明明白白，面试的时候还要手写。但互联网是个神奇的地方，程序员们闲下来之后，创造出了一堆完全不正经、但又莫名符合某种哲学的排序算法。它们有的靠睡觉，有的靠喝酒，有的靠打响指，还有的直接消灭问题本身。

今天就来盘点一下这些广为流传的Meme排序算法。

友情提示：以下算法请勿用于生产环境，否则后果自负。

Stalin Sort（斯大林排序）

先从最著名的开始。斯大林排序的核心思想非常简单粗暴：遍历数组，凡是不服从秩序（乱序）的元素，直接清除。

一趟遍历下来，剩下的元素必然是有序的。时间复杂度 O(n)，比快速排序还快，代价是——数据没了。

def stalin_sort(arr):
    if not arr:
        return arr
    result = [arr[0]]
    for x in arr[1:]:
        if x >= result[-1]:
            result.append(x)
        # 否则,这个元素就"消失"了,没有人见过它
    return result

print(stalin_sort([1, 5, 3, 8, 2, 9]))  # [1, 5, 8, 9]

你看，数组确实有序了，只是3和2再也没有出现过。有人问起，就说它们去西伯利亚出差了。

这个算法告诉我们一个深刻的道理：解决不了问题，就解决提出问题的元素。

Bogo Sort（醉汉排序）

Bogo Sort，也叫猴子排序、醉汉排序。它的思路完美还原了一个醉汉整理扑克牌的过程：把牌全部抛向空中，捡起来，看看有没有序。没有？再来一次。

import random

def bogo_sort(arr):
    while arr != sorted(arr):
        random.shuffle(arr)
    return arr

平均时间复杂度 O(n × n!)，最坏情况是无穷大——理论上你可能洗到宇宙热寂都洗不出有序的序列。但是它也有最好情况：O(n)，一次就中。所以每次运行Bogo Sort，本质上是在测试自己今天的运气。

有人拿它排序过10个元素，等了几分钟；有人拿它排序过20个元素，据说现在还在等。

Sleep Sort（睡眠排序）

这是我个人认为最有灵性的一个，最早出自4chan论坛。思路是：为每个数字开一个线程，数字是几，就睡几秒，睡醒了就输出自己。

小的数字先睡醒，大的数字后睡醒，输出顺序自然就是从小到大。排序这件事，就这样外包给了操作系统的调度器。

import threading
import time

def sleep_sort(arr):
    result = []

    def worker(n):
        time.sleep(n)
        result.append(n)

    threads = [threading.Thread(target=worker, args=(n,)) for n in arr]
    for t in threads:
        t.start()
    for t in threads:
        t.join()
    return result

print(sleep_sort([3, 1, 4, 1, 5, 2]))  # [1, 1, 2, 3, 4, 5]

时间复杂度是多少？O(max(arr))——取决于数组里最大的数。排序 [1, 2, 3] 只要3秒，排序 [1, 2, 86400] 需要一天。如果数组里有负数，那就更刺激了：你需要一台时光机。

它可能是唯一一个复杂度不用 n 表示的排序算法，堪称算法界的行为艺术。

Thanos Sort（灭霸排序）

灭霸排序，出自那个著名的响指。算法流程：检查数组是否有序。无序？打个响指，随机消灭一半元素。重复，直到有序为止。

import random

def thanos_sort(arr):
    while arr != sorted(arr):
        # 完美平衡,一如既往
        arr = random.sample(arr, len(arr) // 2)
    return arr

print(thanos_sort([5, 3, 8, 1, 9, 2, 7, 4]))
# 可能输出 [3, 7],也可能输出 [8],全看缘分

和斯大林排序师出同门，都属于”毁灭派”，但灭霸排序更讲究一些——人家至少是随机的、公平的，而且嘴上还挂着”完美平衡”。最坏情况下数组只剩一个元素，但一个元素的数组必然有序，所以这个算法保证收敛。你看，牺牲一半，换取宇宙的秩序，这买卖多划算。

Communism Sort（共产主义排序）

无序的根源是什么？是元素之间的差异。有大有小，才有乱序。共产主义排序从根本上解决了这个问题：让所有元素相等。

def communism_sort(arr):
    if not arr:
        return arr
    average = sum(arr) // len(arr)
    return [average] * len(arr)

print(communism_sort([5, 3, 8, 1, 9]))  # [5, 5, 5, 5, 5]

时间复杂度 O(n)，空间复杂度 O(n)，稳定性极佳——毕竟大家都一样，谁也别想不稳定。排序后的数组不仅有序，而且是升序、降序同时成立，这是快速排序一辈子也做不到的事情。

没有差异，就没有乱序。从今天起，数组里没有大数和小数，只有平均数。

Capitalism Sort（资本主义排序）

与之对应的是资本主义排序：它不改变任何元素的值，而是让大的更大、排得更前，小的往后稍稍。 等等，这不就是普通的降序排序吗？

不，资本主义排序的精髓在于马太效应——每一轮迭代，大的元素还会从小的元素那里再吸走一点：

def capitalism_sort(arr):
    arr = sorted(arr, reverse=True)  # 先富起来的排前面
    for i in range(len(arr) - 1):
        # 头部元素从尾部元素吸走10%的财富
        tax = arr[-1] * 0.1
        arr[0] += tax
        arr[-1] -= tax
    return arr

print(capitalism_sort([5, 3, 8, 1, 9]))
# [10.62, 8, 5, 3, 0.38] —— 富者愈富,贫者愈贫

排序结束后，数组确实有序了，而且比排序前”更有序”——第一名遥遥领先，最后一名趋近于零。有人说这个算法不公平，但支持者反驳：每个元素都有机会成为第一个元素，只要它出生的时候足够大。

附赠几个冷门选手

盘点完六大门派，再附赠几个同样很有灵性的：

Quantum Bogo Sort（量子Bogo排序）：随机打乱数组，检查是否有序。如果无序，就销毁这个宇宙。根据平行宇宙理论，总有一个宇宙里的数组一次就洗对了，而幸存下来的你恰好就在那个宇宙里。时间复杂度 O(n)，副作用是绝大多数宇宙的毁灭。

Miracle Sort（奇迹排序）：检查数组是否有序。无序？什么都不做，过一会儿再检查。理论依据是宇宙射线可能翻转内存中的比特位，只要等得够久，数组总有一天会”自己变得有序”。这是唯一一个把希望完全寄托于奇迹的算法，适合佛系程序员。

def miracle_sort(arr):
    while arr != sorted(arr):
        pass  # 心诚则灵
    return arr

Intelligent Design Sort（智能设计排序）：这个数组恰好是当前这个排列的概率只有 1/n!，概率如此之低，说明这绝非偶然——这一定是造物主精心安排的顺序。谁是我们凡人，胆敢质疑造物主的排列？因此，数组已经有序了，直接返回。时间复杂度 O(1)，信仰复杂度 O(∞)。

写在最后

盘点下来你会发现，这些Meme算法其实各有各的”哲学”：斯大林排序消灭异见，灭霸排序牺牲一半，共产主义排序抹平差异，资本主义排序放大差异，Bogo排序把命运交给随机，Miracle排序把命运交给上天。

笑归笑，这些算法其实是很好的反面教材：Sleep Sort能让你理解线程调度，Bogo Sort是讲期望复杂度的绝佳例子，Stalin Sort稍微改一改就是求最长递增子序列的引子。所以下次面试官让你手写快排的时候，不妨先反问一句：”您希望是斯大林版本的还是灭霸版本的？”

最后，如果面试挂了，别说你读过这篇blog。