企业官网建设流程全解析

我第一次带新人面试的时候，喜欢让人现场写快速排序。十个候选人里有八个能写出递归版本，写得也基本没错；但只要你多问一句“partition 做完之后，基准元素到底处于什么状态”，能答清楚的立刻少一半。快速排序在数据结构与算法里地位很特殊：它不像冒泡排序那样直白，也不像归并排序那样好解释，但它几乎出现在每一本算法书的“必背清单”里，也是 Java、C++、数据库乃至大数据框架内部绕不开的排序基础。这篇文章我打算从一个老开发的角度，把快速排序彻底拆开讲一遍，从 partition 的根本原理讲到 C 语言和 Java 的完整实现，再到非递归写法、三路快排、三数取中这些工程优化，最后聊聊真实项目里你该怎么选排序方案。不管你是刚学数据结构的学生，还是工作中经常被排序需求折腾的开发者，这篇文章应该都能给你一点新东西。

1. 快速排序为什么快：先啃下partition这块硬骨头

1.1 快速排序的核心：一次partition在做什么

很多人背快排的代码，背了忘、忘了背，问题就出在没理解 partition 这一层。所谓 partition，翻译过来就是“划分”，它的任务很单一：从数组里挑一个元素当基准，然后通过一系列交换，让这个基准元素最终落在它“应该待的地方”。

什么叫应该待的地方？如果数组最终排好序，某个元素在位置 i 上，那么它左边所有元素都不比它大，右边所有元素都不比它小。partition 做完之后，基准元素就恰好满足这个性质。它是一个分界点，把数组劈成两半：左边的小于等于基准，右边的大于等于基准。注意，左右两半内部此时还是乱序的，这不重要，重要的是分界点已经固定了。

我经常用一个生活化例子解释这一步：想象你手里是一摞没有按成绩排序的试卷，你随手抽出一张当作“分界线”，然后让分数比它低的放左边，比它高的放右边。这张分界线试卷的位置从此就固定了，不用再动它。剩下的工作，就是把左右两摞各自再做同样的事情。排序在这里不是“一点点冒泡”，而是“一层层划界”，数据规模每次都能被拆得越来越小。

1.2 分治怎么让数据规模指数级缩小

快速排序用的是典型的分治思想：分解，递归，合并。但快排和归并排序最大的区别在于，快排在分解阶段就完成了核心工作，合并不需要额外操作，因为数据是在原地交换的。归并排序的“合并”阶段最花时间，而快排把功夫花在了“划分”上面。

假设某次 partition 把数组分成了左边大小为 k、右边大小为 n-k-1 的两部分，那么这一次划分的耗时是 O(n)，递归之后的耗时可以用递推式表达：

T(n) = T(k) + T(n-k-1) + O(n)

如果 k 和 n-k-1 差不多大，比如每次都把数组对半分，那么递归深度是 O(logn)，总复杂度 T(n) = O(nlogn)。这就是理想情况。但如果你运气比较背，每次基准元素恰好是最大值或者最小值，那么 k=0，另外一侧是 n-1，递归深度会变成 O(n)，总复杂度退化成 O(n²)。快排能不能跑得快，核心问题就是“怎么避免这种倒霉情况”。

这也是快速排序和冒泡排序、选择排序拉开差距的原因。冒泡和选择每一轮只能确定一个极值的位置，而快排通过一次划分，基准元素落位后天然把问题分成两个独立子问题，后续无需再跨区域比较，少了大量无效工作。同样 O(nlogn) 复杂度的归并排序虽然稳定，但合并阶段需要额外数组，空间复杂度更高；快速排序是原地排序，常数因子更小，对 CPU 缓存也友好。

1.3 复杂度对比：先看清快排在排序家族里的位置

我在带新人时经常画一张表，把常见排序的复杂度和特点列出来，这样在选型时不容易走偏：

从表里能看出，快速排序的优点非常明显：平均速度最快的一档，原地排序不需要额外大数组，递归栈的开销在均匀划分时只有 O(logn)。它的两大命门也写得很清楚：最坏情况 O(n²)，并且不稳定。后面我要讲的非递归、三数取中、三路快排，本质上都是在给这两个命门打补丁。

2. 从零写出快速排序：C语言版和Java版对照

2.1 最经典的Lomuto划分实现

快速排序的 partition 实现有不少流派，最常被教科书采用的是 Lomuto 划分。它思路简洁，代码也短，适合用来理解核心逻辑。

Lomuto 划分的维护逻辑是：用变量 i 指向“小于基准区间”的最后一个位置，用 j 从头到尾扫描未处理的部分。扫描时如果发现某个元素小于基准，就把 i 向后移动一位，并把当前元素换过去。扫描结束后，基准和 a[i+1] 交换，基准就位。

C 语言版本：

#include <stdio.h> void swap(int *a, int *b) { int tmp = *a; *a = *b; *b = tmp; } int partition(int a[], int left, int right) { int pivot = a[right]; int i = left - 1; for (int j = left; j < right; j++) { if (a[j] < pivot) { i++; swap(&a[i], &a[j]); } } swap(&a[i + 1], &a[right]); return i + 1; } void quickSort(int a[], int left, int right) { if (left >= right) { return; } int p = partition(a, left, right); quickSort(a, left, p - 1); quickSort(a, p + 1, right); } int main(void) { int a[] = {9, 2, 5, 1, 7, 6, 8, 3, 0, 4}; int n = sizeof(a) / sizeof(a[0]); quickSort(a, 0, n - 1); for (int i = 0; i < n; i++) { printf("%d ", a[i]); } printf("\n"); return 0; }

这段代码里最值得琢磨的是循环条件j < right。很多新手会写成j <= right，想着把最后一个元素也扫一遍，结果实际操作的时候基准自己参与交换，最终 partition 返回的下标是错的，排序直接乱套。记住：基准是在循环结束后单独交换的，扫描区间永远要排除基准所在的位置。

2.2 Java实现与对象数组排序的坑

Java 版本的结构和 C 版本几乎一模一样：

public class QuickSort { public static void quickSort(int[] arr, int left, int right) { if (left >= right) { return; } int p = partition(arr, left, right); quickSort(arr, left, p - 1); quickSort(arr, p + 1, right); } private static int partition(int[] arr, int left, int right) { int pivot = arr[right]; int i = left - 1; for (int j = left; j < right; j++) { if (arr[j] < pivot) { i++; int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } int tmp = arr[i + 1]; arr[i + 1] = arr[right]; arr[right] = tmp; return i + 1; } public static void main(String[] args) { int[] arr = {9, 2, 5, 1, 7, 6, 8, 3, 0, 4}; quickSort(arr, 0, arr.length - 1); System.out.println(Arrays.toString(arr)); } }

Java 里有一个容易忽略的坑：int[]是基本类型数组，不能直接传给泛型方法，也不能用 Comparator 自定义比较规则；如果要对int[]手写快排，上面的代码就够了。但如果你面对的是Integer[]或者对象数组，想自定义比较规则，就需要自己写Comparator<Integer>，并且在 partition 里调用comparator.compare(arr[j], pivot) < 0来决定是否交换。

更重要的是：快速排序是原地交换排序，它天然不稳定。如果你对一个对象数组排序，而两个对象“相等”是根据某几个字段决定的，partition 过程中的交换完全可能让它们在数组里的相对顺序发生变化。这在某些业务里是不能接受的，所以 Java 的Arrays.sort(Object[])才没有用快排，而是用了稳定、对链表和部分有序场景更友好的 TimSort。而Arrays.sort(int[])这种基本类型数组不关心稳定性，用的是双基准快速排序。语言内置的排序已经在底层替你做了一轮选型，手写快排前要想清楚：你到底需不需要稳定性。

2.3 递归终止条件和边界条件的血泪教训

我见过太多人在快排的边界上翻车，这里列几个真实遇到过的错误场景。

第一个错误是递归终止条件只写if (left == right) return;。当区间只有一个元素时没错，但别忘了还有left > right的情况。比如某次 partition 返回了 left，那么递归右半区间时p + 1可能大于 right，递归左半区间时p - 1可能小于 left。不写>=，就会进入无效递归，虽然不一定立刻崩，但在边界数据上可能造成死循环或数组越界。

第二个错误是递归时把左侧写成quickSort(a, left, p)。表面上看只多包含了一个元素，好像没什么影响，但后果很严重：基准元素 p 已经被放到了最终位置，如果下一次划分又把它当成待排序区间的一部分，一旦输入存在大量重复元素，就可能出现永远无法缩小区间的情况，最终栈溢出或者时间暴涨。正确的写法必须是p - 1和p + 1，把基准排除在外。

第三个错误和递归深度本身有关。假设你写的是固定取最后一个元素当基准，然后给一个已经升序排列的 100 万元素数组排序，每次划分都退化成最坏情况，递归深度接近 100 万。JVM 默认栈深度通常只有几千层，一旦超过就会抛出 StackOverflowError。我自己在压力测试时被这个坑折腾过很多次，后来学聪明了：一是别用固定基准，二是数据量大时改用非递归版本。

3. 非递归快速排序：内存控制与显式栈实现

3.1 为什么要用非递归

很多人在网上搜“快速排序非递归”，第一反应是“面试官故意刁难”。说实话，非递归版本确实在面试里高频出现，但它的价值不仅限于面试。

递归版本的额外空间来自函数调用栈。理想情况下，均匀划分的递归深度是 O(logn)，绰绰有余；但遇到接近有序的数据、基准选择又不够好时，递归深度可能接近 n。即便我们后面会用三数取中降低退化概率，但工程里永远有极端数据，我们不能把系统的稳定性赌在“数据碰巧不坏”上面。比如你写了一个后台服务，每天要排几百个百万级整型数组，某天运维同学导入了一份已经排好序的历史数据，固定基准的朴素快排可能直接让服务线程栈溢出。这种线上事故一旦发生，排查成本远高于提前写稳。

除此之外，非递归版本把待排序区间放到了一个“显式的栈”里，这个栈的大小、压栈策略、处理顺序都是你可以控制的，这给了你更大的调优空间。比如可以只压长度大于 1 的区间，也可以每次先压较大的区间，让栈空间保持 O(logn)，这些都是递归写法做不到的细粒度控制。

3.2 用栈保存待排序区间

非递归快排的思路非常简单：递归的天然行为就是把“还没排好的子区间”压进系统调用栈，那我们就自己准备一个栈，把子区间压进去再循环处理。

import java.util.ArrayDeque; import java.util.Deque; public class QuickSortNonRecursive { public static void quickSort(int[] arr) { Deque<int[]> stack = new ArrayDeque<>(); stack.push(new int[]{0, arr.length - 1}); while (!stack.isEmpty()) { int[] range = stack.pop(); int left = range[0]; int right = range[1]; if (left >= right) { continue; } int p = partition(arr, left, right); if (left < p - 1) { stack.push(new int[]{left, p - 1}); } if (p + 1 < right) { stack.push(new int[]{p + 1, right}); } } } private static int partition(int[] arr, int left, int right) { int pivot = arr[right]; int i = left - 1; for (int j = left; j < right; j++) { if (arr[j] < pivot) { i++; int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; } } int tmp = arr[i + 1]; arr[i + 1] = arr[right]; arr[right] = tmp; return i + 1; } }

这里用Deque<int[]>做栈，每个元素是一个长度为 2 的区间。压栈前手动判断区间长度是否大于 1，能减少无效循环。需要注意压入顺序不会影响最终结果，因为每个区间彼此独立，无论哪个先处理都会得到正确排序结果。但如果你关心栈的最大深度，可以让较长的区间先入栈、较短的区间后入栈，这样栈中待处理的区间数量更容易维持在 O(logn)。

3.3 非递归版本实测：栈大小、性能差异

我用 100 万随机整数做过一次简单对比，递归版本和非递归版本在耗时上没有明显差别，基本都在同一数量级。真正拉开差距的场景是“有序数据 + 固定基准”：递归版本在十几万数据时就开始栈溢出，而非递归版本虽然也慢，但不至于直接崩溃。这个实测结果说明，非递归不是“性能银弹”，它解决的是健壮性问题，而不是速度问题。如果你发现非递归比递归慢一点点，那是因为每次区间进出栈多了一些对象创建开销，可以用两个独立的栈分别存 left 和 right 来优化，但绝大多数场景不差这点开销。

还有一点值得注意：递归版本的 O(logn) 空间指的是“理想划分”下的栈深度，而非递归版本的空间也是 O(logn)，只不过它占用的是堆内存。在 Java 里堆内存通常比栈内存大得多，所以同样深度，堆上的栈能扛住的压力远大于递归栈，这也是非递归在工程里更稳的底层原因。

4. 快排的工程级优化：从三数取中到三路快排

4.1 基准选择不当会让快排变成冒泡排序

我已经反复提到最坏情况，这里具体演示一遍为什么固定基准这么危险。输入是升序数组[1, 2, 3, 4, 5, 6, 7, 8, 9]，代码里固定取a[right]当基准，第一次 partition 的基准是 9。9 是最大值，小于它的元素全在左边，partition 结束后 9 还在最右边，位置和原来一模一样。然后递归处理左边[1..8]，基准又变成 8，还是最大值，同样只挪动一个位置。整个排序过程递归深度就是 n，每一层划分复杂度 O(n)，最终 O(n²)。

这和冒泡排序的处境很像，每一步都在处理一个几乎没变化的区间。更麻烦的是，递归深度 n 会让栈先爆掉，所以表现比冒泡还要难看。解决思路是让基准更接近“中位数”，常见做法是随机选基准或者三数取中。随机选在数学上能让退化概率变得极低，但如果数据碰巧随机数每次都命中最小值，也会退化，只是概率小到可以忽略；三数取中则更稳定，代码也容易控制。

三数取中的做法：取区间最左、中间、最右三个元素，把它们的中间值当成基准。代码实现时先把三个数排序，再把中位数交换到right位置，后面就可以继续复用原 partition。

void quickSortMedian(int a[], int left, int right) { if (left >= right) { return; } int mid = left + (right - left) / 2; if (a[left] > a[mid]) swap(&a[left], &a[mid]); if (a[left] > a[right]) swap(&a[left], &a[right]); if (a[mid] > a[right]) swap(&a[mid], &a[right]); swap(&a[mid], &a[right]); int p = partition(a, left, right); quickSortMedian(a, left, p - 1); quickSortMedian(a, p + 1, right); }

这段代码里有个细节：取中间位置时写成left + (right - left) / 2，而不是(left + right) / 2。后一种写法在 left 和 right 很大时可能整型溢出，虽然排序场景数组长度通常到不了溢出级别，但这是一个值得养成的编码习惯。

三数取中并不能彻底消除最坏情况，它只是让“选到极值”的概率大大降低。比如构造特定数据仍然可能让三数取中失效，业界更稳妥的做法是再加上一颗“安全网”：当递归深度超过某个阈值时切换到堆排序。这就是 C++std::sort采用的 Introspective Sort 策略，后面我会再提到。

4.2 大量重复元素：三路快排

如果说三数取中解决的是“有序数据退化”，三路快排解决的是“大量重复元素浪费”的问题。

假设数组里 1000 万个元素全部相等。朴素快排会怎么做？每次 partition 选出基准后，小于基准的没有，大于基准的也没有，基准只归位了一个元素，然后递归处理剩下的 9999999 个元素。这会导致 O(n²) 级别的行为，虽然实际情况比最坏好一些，但依旧非常浪费。Dataset 一旦变成“全部相同”这种极端分布，朴素快排性能会惨不忍睹。

三路快排的核心是把数组一次划分为三块：“小于基准”“等于基准”“大于基准”。等于基准的元素在划分后直接跳过，不再参与任何递归。这种思路在网上常被称为荷兰国旗问题，因为官方定义就是把数组按红白蓝三色分成三段。

public static void quickSort3Way(int[] arr, int left, int right) { if (left >= right) { return; } int pivot = arr[right]; int lt = left; int i = left; int gt = right; while (i <= gt) { if (arr[i] < pivot) { swap(arr, lt, i); lt++; i++; } else if (arr[i] > pivot) { swap(arr, i, gt); gt--; } else { i++; } } quickSort3Way(arr, left, lt - 1); quickSort3Way(arr, gt + 1, right); } private static void swap(int[] arr, int i, int j) { int tmp = arr[i]; arr[i] = arr[j]; arr[j] = tmp; }

这段代码里三个指针的含义要理解清楚：lt 指向“小于区”的最后一个位置的下一个位置，gt 指向“大于区”的第一个位置的前一个位置，i 负责从 left 向右扫描。当arr[i] < pivot时，把它换到 lt 位置，lt 和 i 一起后移；当arr[i] > pivot时，把它换到 gt 位置，gt 左移，但 i 不动，因为换过来的新元素还没被检查；当arr[i] == pivot时，i 直接后移。等循环结束时，[left, lt-1]是小于区，[lt, gt]是等于区，[gt+1, right]是大于区。

三路快排在随机数组上会比普通快排稍慢一点，因为多了一些额外交换；但在重复元素占比高的场景下优势巨大。JDK 的Arrays.sort在底层对特定类型也会使用类似思路的排序策略，这也说明工程实现从来不是只认一种排序算法。

4.3 小规模区间用插入排序收尾

很多刚学排序的人不理解：为什么快排递归到小区间后要切回插入排序？插入排序平均不是 O(n²) 吗，为什么反而更快？

答案在于常数因子和数据局部性。快排在递归过程中每次调用 partition 都有函数调用开销、交换开销；当区间长度很小，比如 10 个元素时，partition 带来的复杂度收益已经不明显，而插入排序因为代码简单、内存访问连续、没有递归调用，实际跑起来反而更快。这就像长距离运输选火车，但最后一公里要用小推车，不能因为火车运力大就一直开到别人家门口。

实现思路很简单：在 quickSort 的递归开头判断区间长度，如果小于某个阈值（常见取 8 到 16 之间）就调用插入排序，不再继续 partition。

private static void insertionSort(int[] arr, int left, int right) { for (int i = left + 1; i <= right; i++) { int key = arr[i]; int j = i - 1; while (j >= left && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } }

这是一项纯工程优化，不改变复杂度的大 O 级别。它为快排省下的是最后一层深度的递归调用和大量无谓交换，实测在小规模区间切换后，随机数组排序时间能再快 10% 到 20%，而且代码逻辑不复杂，非常划算。

4.4 优化前后对比

为了讲清楚这些优化到底带来多少收益，我用一组规模为 100 万的整型数组做过粗略测试，下面给出的是相对耗时感受，不是绝对毫秒数，不同机器上会有差异：

这张表的核心结论是：三数取中负责“防退化”，三路划分负责“处理重复元素”，插入排序负责“抠常数”。三者叠加以后，快排在绝大多数数据分布下都能跑得很稳。

5. 快速排序在真实项目里的选型与变体

5.1 为什么JDK的Arrays.sort不是纯快排

很多人看到 Java 的Arrays.sort底层是 DualPivotQuicksort，就以为 JDK 用的是快排。这个说法不够准确。Arrays.sort(int[])确实用了双基准快速排序，而且还会在数组很小的时候使用插入排序；但Arrays.sort(Object[])用的却是 TimSort，这是一种改进版归并排序。

为什么要区分？底层原因是稳定性。对int[]这样的基本类型，排序结果里元素不可区分，谈稳定性没有意义；但对象数组排序时，两个对象可能根据比较器被视为“相等”，稳定的含义是它们排序后仍然保持原始相对顺序。归并进行合并时可以做到稳定，快排的原位交换则很难保证稳定，所以对象排序选择了 TimSort。

C++ 的std::sort又是另一种思路：它使用 Introspective Sort，主体是快速排序，但会监控递归深度，当深度超过2 * log2(n)时切到堆排序兜底。这样既保留了快排的平均性能优势，又封死了最坏情况退化的门。工程语言内置排序基本上都是这种“多算法组合”的思路，没有人会天真地拿一个朴素快排直接怼生产环境。

5.2 稳定性需求：对象排序与sort的约定

快速排序不稳定这件事，平时写算法题看不出来，但业务里一旦踩坑就是隐性 Bug。举个例子：你先给订单按创建时间排序，再给订单按客户等级排序，如果第二次排序是稳定的，那么同一个客户等级的内部仍然保持按时间有序；如果第二次排序不稳定，这些订单顺序可能被打乱，用户看到的列表就会“莫名奇妙地乱跳”。

Java 里表达对象排序最方便的还是 Comparator。你可以链式定义多字段规则：

users.sort( Comparator.comparing(User::getAge) .thenComparing(User::getName) );

这段代码底层走的不是快排，而是 TimSort，所以它稳定，可以安全支持“先按 A 排，再按 B 排”的多级排序。但如果你因为某种原因需要手写排序，比如在面试中、在内存极受限的环境里、或者底层是int[]这种基本类型数组，你就要意识到快排会破坏稳定性，这时必须评估你的业务是否依赖原始顺序。选择排序和希尔排序也不稳定；插入排序和归并排序则天然稳定。理解这些区别，比背下任何一个排序代码都更重要。

5.3 大数据与数据库排序：快排思想如何渗透

搜索热词里有一大堆关于“MapReduce 排序”“自定义排序”“分组排序”“倒排序索引”的提问，很多做数据开发的朋友看到这些会很困惑：这些和快速排序有关系吗？

有关系，但关系在思想上，不在代码实现上。外部排序因为数据量放不进内存，主流手段是归并：先分块读入内存、每块内部排好序，再做多路归并。这里“块内排序”用什么算法都行，工程上常用快排，因为它在内存里更快；而整个世界的数据分区、归并方式又是归并思想。MapReduce Shuffle 阶段的排序、Hive 里的 Order By、SQL 里的 ORDER BY，底层都是“局部排序 + 整体归并”的组合。很多搜索引擎的倒排索引排序，也会先用 partition 风格的思路做数据分片。

如果你想在这些框架里自定义排序规则，核心动作通常是实现一个比较器。比如 Hadoop 里实现WritableComparator，或者用自定义的 Key 来改变分组和排序顺序。表面看是调框架 API，实际你写的每一个比较器，最终都会被排序引擎在你指定的规则下反复调用，不管底层是快排还是 TimSort，比较器的语义都必须严格一致，否则排序结果会匪夷所思。理解快排的 partition 逻辑，能帮你更好地理解这些分布式排序里“分区”这一步到底在干什么。

5.4 字符串、多字段排序时怎么用快排思路

关于字符串排序和“字母数字组合的排序”，通常要拆成两个层次来看待。第一个层次是语言层：比如 JS 里Array.prototype.sort()默认把元素转成字符串再比较，所以对数字数组直接排序会得到荒诞结果；正确做法是传入数字比较器(a, b) => a - b。V8 引擎底层用的是稳定排序，但很多人写代码时不传比较器，结果字符串排序“看起来差不多、细节全错”。第二个层次是算法层：如果字符串数量特别巨大，而且共享大量公共前缀，普通快排每次比较两个字符串都要从头扫描字符，代价不低，有一种变体叫三向字符串快速排序，它正是利用三路快排的思路，把字符小于、等于、大于基准字符的元素分成三组，只对中间“等于前缀”的组继续深入比较下一个字符。这个思路在字符串排序场景比普通快排强很多。

多字段排序也是一样的逻辑：你定义了一个“比较规则”，这个规则最终决定了任意两个元素谁前谁后。无论你用的是手写快排还是内置排序，只需要把 partition 里那个硬编码的arr[j] < pivot换成“根据比较规则判断小于”，其余逻辑完全不变。这就是为什么我建议你一定要理解 partition 的本质：它不是只能比较整数，而是可以通过抽象的比较器适配任何数据。

我个人这些年写下来最大的体会是：算法题里的快排只是冰山一角，真正值钱的是你看到数组时能想到概率退化，看到重复数据时能想到三路划分，看到对象排序时能想到稳定性，看到自带的 sort 时能想到它背后为什么是多种算法的组合。这种“地图感”不会一天练成，但一旦建立起来，以后再遇到任何和排序沾边的需求，你都不会慌。如果你现在正在背快排代码，别急着背优化版本，先把 Lomuto 划分写在纸上，把每个变量的变化过程走一遍，然后把递归改成栈，把固定基准改成三数取中，再试试三路快排处理重复元素，一路走下来，你就真的把这个算法吃透了。