我发现了一个 “暴力又高效” 的排序算法：斯大林排序（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)”，你可以笑着回一句：“那你是用了斯大林排序吧？”

如果你正在学习python，这些Python资料、数据分析、Python从入门到实践第三版pdf书籍、Python+Pycharm安装包&永久激活插件、直播课程，可以在这里免费领取哈👇