🎮 装备分拣：一行流的诱惑与分桶的正道

“小白！”村长一脚踹开大门，怀里抱着一堆闪闪发光的装备，“昨晚勇士团连夜刷副本，爆了一地装备！你看这战力值——[9, 12, 5, 10, 14, 3, 10]。现在要以战力 10 为基准分三批：比 10 弱的给新手村，等于 10 的放仓库备用，比 10 强的给精英团。而且同一批装备必须按掉落顺序排列——这样好查记录，知道是哪只 BOSS 爆的！”

我接过装备清单扫了一眼，这不就是稳定三路划分吗？快排里的 partition 一个原地交换下去，相同元素的先后顺序直接乱套——这里要求组内保序，那就不能原地搞了，得上辅助空间。三个桶，一趟遍历：比 pivot 小的进左桶，相等的进中桶，大的进右桶。从左往右依次遍历，每个桶天然保持原数组的先后顺序。

正准备掏分桶代码，我脑子突然一抽：等等，Python 的 sort 不是稳定排序吗？Timsort 亲口承诺“相同键值保序”，那我直接用 key 函数把小于 pivot 的映射成 -1，等于的映射成 0，大于的映射成 1，然后排一遍不就行了？一行流，帅就完事。

nums.sort(key=lambda x: (x > pivot) - (x < pivot))

跑样例，输出完美。提交，AC 弹出。我往椅背上一靠，翘起二郎腿，心里已经开始给自己加戏——一行代码搞定装备分拣，村长直呼内行，精英团连夜给我加 Buff，仓库管理员感动得要把女儿许配给我。

正美着，后脑勺“啪”地挨了一下。

回头一看，老勇者叼着棒棒糖站在我身后，手指还保持着弹脑瓜崩的姿势。“你觉得这就算写完了？”

“AC 了啊！”我捂着后脑勺，指着屏幕上的绿色大勾。

“AC 不代表没毛病。”他点了点屏幕，“你这 sort，时间复杂度多少？”

“O(n log n)……”我声音小了一半，后脑勺还隐隐作痛。

”题目让你分组，不是让你排序。分组是 O(n) 的活——看一眼战力值，扔进对应的箱子，完事。你调 sort，等于雇了个全职排序师来当门卫。排序引擎不知道你只想分堆——它勤勤恳恳地比较、归并、插入，log n 层递归树跑满，就为了完成一个你早就知道答案的任务。而且 Timsort 底层 merge 要临时数组，额外空间也是 O(n)——你这一行流，时间复杂度输了，空间也没省。”

他把棒棒糖往嘴角一叼：“一行流看着帅，语义不对。用排序引擎做分组，技术债，利息 O(n log n)。哪天副本掉了一百万件装备，Boss 都刷新两轮了你的代码还在排序，勇士团站门口干等，回头差评全写你名字。”

我脸上的得意全部转移到了脚趾上。我默默地把那一行流注释掉，老老实实掏出了分桶三数组的写法：

遍历整个装备列表，比pivot弱的扔进 left 箱发往新手村；相等的扔进 mid 箱存仓库；比pivot强的扔进 right 箱送精英团。因为是从左往右按掉落顺序依次遍历的，每个箱子里的装备天然保持了原来的先后顺序，最后把三个箱子的装备按顺序拼接，分拣完毕：

def pivotArray(self, nums: List[int], pivot: int) -> List[int]:
    left, mid, right = [], [], []
    for x in nums:
        if x < pivot:
            left.append(x)
        elif x == pivot:
            mid.append(x)
        else:
            right.append(x)
    return left + mid + right

O(n) 时间，O(n) 额外空间，语义清晰，逻辑直白。村长看了眼分好的三箱装备，满意地点点头，抱着箱子去仓库贴标签了。

老勇者看着我把分桶版本提交上去，这次没弹脑瓜崩，点了点头：“记住，一行流能 AC 不代表它是最优解。sort 是通用排序，它不知道你只想分堆。能现场分组的，就别排序。”

我揉着后脑勺，默默记下了。但盯着那三个桶，还是忍不住追问了一句：“空间复杂度有没有优化空间？”

老勇者瞥了我一眼：“你愿意拿时间换，就可以。”

“原地交换加插入排序，能压到 O(1) 空间——每遇到一个元素，先判断它该去哪边，再用位移操作把它挪到对应位置，保证组内顺序不变。但每次挪位置都是 O(n)，总复杂度 O(n²)。O(1) 空间换 O(n²) 时间，等于徒手搬一百趟装备省一个空间戒指，血亏。”

他把棒棒糖往嘴里一叼，拍了拍我肩膀：“编程跟打副本一个道理——理解机制比硬刚更重要。稳定分区必须付出代价，要么付空间，要么付时间。n ≤ 10⁵ 的数据量，O(n) 空间换 O(n) 时间是血赚。省空间的念头，留着对付那些不要求稳定性的题——那才是原地交换大展拳脚的地方。”

窗外，勇士团扛着新到货的装备箱浩浩荡荡走过，村长跟在后面一路小跑，手里还抱着我分好的三摞清单。我把魔法书翻到今天这一页，在旁边批了三行：能分组的，就别排序。稳定分区，空间换时间是正道。

本作品采用 知识共享署名-非商业性使用-禁止演绎 4.0 国际许可协议 进行许可。