拆解Python斯大林排序算法：O(n)时间复杂度的“梗”式实现

我发现了一个“暴力又高效”的排序算法：斯大林排序（Stalin Sort）。

你见过 O(n) 时间复杂度 的排序算法吗？不是快排，不是归并，而是一个玩梗玩到极致的“政治玩笑算法”—— 斯大林排序（Stalin Sort）。

今天我们就来拆解这个魔性算法，看看它为什么能在程序员圈子里火出圈。

什么是斯大林排序？

先看定义：

扫描数组时 仅保留非递减前缀，任何小于当前最大值的元素都会被“清除”。

说白了：

1. 从左往右遍历数组
2. 只留下 比之前所有数都大/相等 的元素
3. 不听话的、破坏“递增秩序”的，直接删掉

举个例子：原数组： [3, 1, 4, 1, 5, 9, 2, 6]
斯大林排序后： [3, 4, 5, 9]
你看，1、1、2、6 都因为“不够大”被清除了，剩下的就是一个完美的非递减序列。

Python 实现：一行都不多写

这是最简洁的 Python 版本，没有任何注释，干净利落：

def stalinSort(arr):
    if len(arr) == 0:
        return []
    kept = [arr[0]]
    maxSoFar = arr[0]
    for i in range(1, len(arr)):
        if arr[i] >= maxSoFar:
            kept.append(arr[i])
            maxSoFar = arr[i]
    return kept

复杂度分析：为什么说它“高效”？

• 时间复杂度：O(n) 只需要遍历数组一次，没有嵌套循环，这是排序算法里的理论极限。
• 空间复杂度：O(n) 最坏情况（数组已经是非递减）需要保存所有元素。

对比一下：

你会发现：斯大林排序用“丢失元素”的代价，换来了线性时间，这也是它的梗点所在——为了“秩序”，不惜牺牲一切。

斯大林排序虽然是个玩笑，但它背后藏着一个深刻的算法思想：约束越少，效率越高。

下次有人跟你吹“我的算法是 O(n)”，你可以笑着回一句：“那你是用了斯大林排序吧？”