快排技术教程

快排这名字听着吓人，快排其实就是技术教程把一堆乱糟糟的数据，按大小排成一条直线。快排平均复杂度O(n log n)，技术教程最坏情况O(n²)，快排但别怕，技术教程大部分时候它快得离谱。快排我见过不少新手一上来就背代码，技术教程背完就忘，快排忘了再背——没用。技术教程你得先搞懂它到底在干嘛。快排

核心就一句话：选一个基准数，技术教程把比它小的快排扔左边，比它大的技术教程扔右边，然后左右两边各自重复这个过程。快排递归嘛，像剥洋葱，一层层剥到只剩一个元素，排序自然完成。举个具体例子，你手里有[5, 3, 8, 1, 9, 2]，随便挑个基准，比如取第一个5。拿两个指针，一个从左边找比5大的，一个从右边找比5小的，找到了就交换位置。左指针停在8，右指针停在2，换一下，数组变成[5, 3, 2, 1, 9, 8]。继续走，左指针再往前，碰到9，右指针往左，碰到1，但这时候左指针已经跑到右指针右边去了，停。把基准5和右指针指的1交换，得到[1, 3, 2, 5, 9, 8]。你看，5左边的全比它小，右边全比它大。接下来对[1, 3, 2]和[9, 8]分别递归，完事。

代码写起来不长，但有个坑我踩过好几年：基准选不好，性能直接崩。比如你拿一个已经排好序的数组，每次基准都选第一个，那递归深度就变成n，退化成冒泡排序，O(n²)妥妥的。我当年在项目里处理用户日志，数据量上百万，没注意这点，接口直接超时，被领导骂得狗血淋头。后来学乖了，要么随机选基准，要么选左中右三个数的中位数。随机最省事，虽然理论上还有概率选到最差基准，但实际中几乎不可能。中位数法更稳，但多几次比较，开销也不大。我个人的习惯是，数据量小于10的时候直接换插入排序，递归到底层太浪费了，函数调用栈都够呛。

写快排还有个细节，就是交换操作。别用额外的数组去存左右分区，那样空间复杂度变成O(n)，快排就失去意义了。原地交换，用临时变量，或者用Python那种a, b = b, a的语法糖，干净利落。我见过有人用列表推导式硬写快排，三行搞定，看起来炫酷，但每次递归都新建list，内存翻倍，数据一大就炸。别学那个，面试装个逼还行，生产环境得务实。

快排的边界条件也容易出鬼。递归函数里，如果left >= right，直接return，不然会无限循环。我刚开始写的时候，漏了等号，结果数组长度是偶数时，左右指针永远碰不到头，程序卡死。调试了半小时，最后打印每一步的索引才看出来。这种错误，光靠看代码很难发现，必须跑起来测。你写快排的时候，建议先拿几个小数组手动走一遍流程，再上机跑随机测试，别嫌麻烦。

最后说点实战经验。快排不是万能的，数据量小的时候，插入排序反而更快，因为递归开销大。数据量大的时候，快排的递归深度可能超过栈上限，比如Java里默认栈深度也就几千，你排个十万个元素，递归调用栈可能溢出。这时候要么改成非递归版本，用显式栈模拟，要么用归并排序。我做过一个排序服务，面对不同大小的请求，直接写了个策略：小于50条用插入，小于10000条用快排，更大的切分后用归并。效果不错，平均响应时间降了30%。快排是工具，不是信仰，别硬用。