快排：不排队也能排开大费事 想象一下，你手里攥着一堆乱糟糟的垃圾，哪怕是一个人，想把它全都扔进垃圾桶。

你看着它们，认定有用是好的，没用到是坏的，中间夹着东西也认定烦。

这时候，你一般不会累得直不起腰去挨个挪动。便，你选了一种随机往旁边一推的动作，然后打住。

如何样，这感觉像不像现场版的快排？ 这就是快排最核心的逻辑：不保证顺序，但保证速度。 在算法的世界里，快排（Quick Sort）实际上是个在竞赛里被捧得高高的名字，但在大多数人的眼里，它就是个“随机乱走”的傻瓜。它不是按顺序来，而是像扔硬币一样，把中间那个数甩到一边，左边小的去那边，右边大的去那边。它不维护“有序”，它只追求“快”。 要是你非要给它起个正经名字，不如叫它“随机走位法”。它的名字听着高大上，用起来却像个毫无章法的混蛋。它不关心你期望拿到的是升序还是降序，它只在乎你愿意付多少代价。 为啥叫“快排”？出于它的平均性能确实快，是 O(n log n)，跟冒泡排序的 O(n²) 比，简直是两个世界的差距。

哪怕你给程序员开了个“优化模式”，让它每次都挑中间那个数，要么每次都挑最大的，它的核心机制依然是那个“随机化”，用来规避最坏的情况。 这就好比你去超市买水。你挑一瓶水，放下就走。你去楼下买瓶，再挑一瓶。你根本不在乎这瓶水和那瓶水是不是放在同一个货架上，也不在乎它们是不是按瓶子大小排好。你不在乎，你只在乎你能买多少。 算法里的概念翻译成人话，就是这种“不在乎”。它不在乎三个数哪位大哪位小，它只在乎能不能把大难题拆成小难题解决。它会把大难题拆成两个子难题，每个子难题又再拆下去，直到那些子难题小到“没啥可拆的了”。

比如你手里有 100 个零件，拆到只剩 2 个，这时候就没有必要再拆了，直接手拉手凑成一对卖。 这时候，你就得拍板如何凑。你能够试着凑最大的，要么试着凑最小的。你随意试一个试试运气，要么干脆来个“暴力战术”。 暴力战术就是：不管三七二十一，先把自己手里的零件按大小排个序，再和剩下的拿。 这听起来像个死循环，并且效率极低。出于第一步你排序花了不少力气，剩下的零件又得再排一轮，结局你实际上啥都没做。 故此，快排务必得有个“脾气”。它不能复读机，它务必得随机。

这就好比你在超市买水，你本来想按瓶子大小排，便你去 A 区挑，挑出来放那，再去 B 区挑，挑出来也放那。你这样折腾个半小时，可能只买到了几瓶不一样的。 但你要是换个策略，你去 A 区挑，挑出来放那，再去 B 区挑，这次去 C 区，挑出来也放那。

哎，这时候你只买了三瓶，但瓶子大小全乱了。 这时候，你就得找个裁判。裁判就是快排的灵魂。你随意挑一瓶，把它扔给裁判，裁判告诉你：这瓶最大的。

然后你再去比它，又扔给裁判，裁判告诉你：这瓶第二大的。 你看，裁判绝对不会说“我没看到那个最大的”，出于它看到了所有瓶子的大小。它不关心你从哪出发了，也不关心你下了多大力气。它只是静静地坐在那，等着人来报数。 快排就是如此个东西。它把“随机化”给了排序算法（比如那个随机选中间数），把“有序”硬塞进了递归的过程（比如递归地按大小分），最终由“裁判”来确保结局是确实最大，而不是只是看起来像最大。 这就好比你在超市买水，你挑一瓶，扔给裁判，裁判说这是最大的。裁判对你来说是个透明的，它不关心你从哪出发的，也不管你下了多少力气，它只是静静地告诉你那瓶水的地位。 再举个例子，假设你手里有 100 个零件，你想把它们按大小排好。你随机挑一个，比如是 50 号。你把它扔给裁判，裁判说“这是最大的”。

然后你再挑一个，扔给裁判，裁判说“这是第二大的”。 这时候，你就发现一个有趣的现象：50 号这个数，在你挑的时候，它既可能是最大的（出于你先挑到的），也可能是第二大的（出于你后来又遇到了一个更大的）。 这就叫“随机化”。它在保证你最终能拿到一个对的结局（有且只有一个最大值，有且仅有一个次大值）的与此同时，最大程度地削减了运气成分。 你当作快排就是靠运气排好的？自然不是。

你看，要是运气极差，你每次挑到的都是最大的那个，那剩下的又都会变成次大的，最终的结局就是“次大、次大、次大……"，别看数量对了，可是哪位也不是第二大。 这时候，快排就得靠裁判了。裁判确保你挑到的确实是最大的，然后把剩下的所有小于它的零件都扔给它。它确保剩下的零件里，确实有一个是次大的，然后持续挑，持续扔。 整个过程就像一个传话筒。你传一个，裁判传一个，最终剩下的那些小零件，还得持续传下去。 并且，快排有个绝活，叫做“分治”。它不是一次就把所有零件排完，而是把它分成两半，左半边排到一半，右半边排到一半，再轮流处理。 你能够随意挑个位置，比如第 50 个零件。把它扔给裁判，裁判挑出它右边的所有零件，扔回来。裁判告诉你：“这里面的数都大于你的数”。

然后你再挑剩下的，要么挑刚刚扔回来的，都是大于你的。 这时候，你就懂了。快排不是靠“随机”来保证结局的准性，而是靠“分治”把难题规模一次次地压缩。它把一个大难题，拆成两个小难题，每个小难题再用同样的方式拆，直到小到不能再拆为止。 这就像你在超市买水，你挑一瓶扔给裁判，裁判说这是最大的。

然后你再挑另一瓶，裁判说这是第二大的。裁判一直往下比，直到最终剩下的那些小瓶子，你也把它们都比了一遍。 这时候，难题来了。当只剩下两个瓶子的时候，如何把它们排好？ 这时候，快排就显露出了它真正的幽默感。它不再随机挑，而是直接说：“嘿，你看这俩瓶子哪位大哪位小，你说了算。” 它不渲染气氛，它直接给个答案。它告诉你：“这个比那个大。”然后它持续处理剩下的，直到最终两个瓶子也排好了。 这时候，你才明白，快排不是个傻瓜。它是个贼高效的“找茬机器”。它不追求结局的完美有序，它只追求过程的极致精简。 它不关心你希望拿到升序还是降序。它只关心你能否利用“分治”和“随机”来把难题拆得越来越小，直到变成能够手动的规模。 它像那个在超市的裁判，它不关心你如何买，也不关心你下了多大力气，它只关心哪位是大，哪位是小，然后告诉你：“这就是答案。” 快排就是靠这种“不在乎”带来的“快”。它不在乎顺序，但它不浪费工夫在“随机”上，出于它把随机化变成了“分治”的基础。 它不保证顺序，但它能保证不浪费工夫在“暴力”上。 故此，下次当你看到快排的时候，别盯着它那个复杂的代码结构看。盯着那个随机数，盯着那个裁判，盯着那个把大难题拆成小难题的滑稽动作就好。 它就是不排队也能排开大费事的魔法。