很多人学数据结构排序算法是绕不开的第一道坎而快速排序又是其中“面试常问、笔试常考、工作常写”的一个。说它在数组上实现值得单独写一篇是因为数组本身是连续内存结构快速排序的分区操作天生依赖随机访问这两者配合起来效率极高但同时也带来不少隐蔽的坑边界写错、递归死循环、重复元素退化、指针数组排序排了个寂寞……这些我都踩过。这篇文章就把快速排序在数组上的实现从头到尾拆一遍包括分治原理、Lomuto和Hoare两种分区写法、三数取中优化、重复元素场景的改进再把数组相关的指针、切片、多维数组这些容易翻车的地方一并讲清楚。不管你是准备笔试的学生还是工作中需要手写排序的开发者都可以直接按这篇文章的思路去写代码。1. 快速排序的分治思想与数组特性1.1 为什么快速排序和数组这么合拍快速排序的思路一句话就能讲完选一个基准元素把数组分成“小于基准”和“大于等于基准”两部分然后对左右两部分递归地做同样的事情直到区间里只剩一个元素。这个思路称为分治和数组这种数据结构可以说是天作之合。原因在于数组的两个特性。第一是随机访问的时间复杂度是 O(1)快排的分区过程需要反复读取某个下标的元素并且原地交换数组天然支持这种操作。第二是缓存局部性数组元素在内存里是连续排列的分区时扫描某个范围内的元素访问的地址基本都集中在相邻内存区域CPU 缓存命中率高实际跑起来远比理论分析还要快。对比一下就明白了如果数据存在链表里快排要从头遍历才能找到某个位置的元素分区一次就需要 O(n) 次遍历定位整体复杂度直接退化成 O(n log n) 变 O(n² log n) 级别的操作量完全得不偿失。所以你会看到链表排序场景几乎都用归并排序而数组排序场景才把快速排序当作首选这不是偶然是数据结构特性决定的。理解了这层关系你才会明白为什么“快排在数组上实现”是一个值得认真研究的题目而不是简单的背代码。1.2 一趟分区到底在数组上做了什么很多人背快排代码背得很熟但问他“一趟分区结束后数组变成了什么样子”就说不清楚了。这不行手写快排出错的根源几乎都是对分区过程缺乏直觉。以最简单的 Lomuto 分区为例假设数组是[7, 2, 9, 1, 5]选最后一个元素 5 作为基准。分区要做的事是从数组开头开始维护一个“已处理的小于基准的区域边界”指针 i另一个指针 j 负责遍历剩下的元素。遇到小于 5 的元素就把它和 i 位置的元素交换i 后移一位遇到大于等于 5 的j 继续走。遍历结束后把基准元素 5 交换到 i 的位置此时 i 左边全是小于 5 的i 右边全是大于等于 5 的返回 i 作为分割点。实际推演一遍会非常直观。初始时 i0j0第一个元素 7 大于 5不交换j1 时元素 2 小于 5交换 a[0] 和 a[1]数组变成[2, 7, 9, 1, 5]i 变成 1j2 时元素 9 大于 5跳过j3 时元素 1 小于 5交换 a[1] 和 a[3]数组变成[2, 1, 9, 7, 5]i 变成 2最后把 a[4] 的 5 换到 a[2]数组变成[2, 1, 5, 7, 9]。一趟下来基准 5 就位左边[2, 1]都小于 5右边[7, 9]都大于 5。关键在于理解 i 的含义它始终指向“下一个放小于基准元素的位置”所以 i 左边的元素全部小于基准j 到区间末尾的元素是还没扫描的。最后一步交换基准到 i是因为 i 此时正好是“第一个大于等于基准的元素”的位置。把这个过程在纸上画一遍比看十遍代码都管用。2. 快速排序的落地实现三种语言完整对照2.1 Lomuto 单边扫描最容易写对的版本先从 Lomuto 分区开始因为它代码最短边界最容易理解非常适合新手手写。public class QuickSort { public static void quickSort(int[] arr, int low, int high) { if (low high) { return; } int pivotIndex partition(arr, low, high); quickSort(arr, low, pivotIndex - 1); quickSort(arr, pivotIndex 1, high); } private static int partition(int[] arr, int low, int high) { int pivot arr[high]; int i low; for (int j low; j high; j) { if (arr[j] pivot) { swap(arr, i, j); i; } } swap(arr, i, high); return i; } private static void swap(int[] arr, int i, int j) { int temp arr[i]; arr[i] arr[j]; arr[j] temp; } }这段代码有一个特别容易写错的地方for 循环的条件是j high不能写成j high。因为arr[high]是基准本身如果 j 也扫描到它遇到自己的时候arr[j] pivot永远不成立相等不会进入交换分支倒也不会出错但会影响你对边界逻辑的理解而且一旦你把基准元素在循环里提前交换走后面就全乱了。我见过不少人把基准元素设为arr[lo]然后循环里又忘了跳过第一个位置结果基准被移动到不知道哪里分区彻底失效。Python 版本的写法核心逻辑完全一样def quick_sort(arr, low, high): if low high: return p partition(arr, low, high) quick_sort(arr, low, p - 1) quick_sort(arr, p 1, high) def partition(arr, low, high): pivot arr[high] i low for j in range(low, high): if arr[j] pivot: arr[i], arr[j] arr[j], arr[i] i 1 arr[i], arr[high] arr[high], arr[i] return iC 语言版本把数组退化成指针后要格外小心int* arr传入partition后arr其实是指向堆内存或栈数组首元素的一个指针arr[high]等价于*(arr high)千万别把下标和指针自增搞混。写 C 版本时我习惯在分区函数里加一个断言assert(i low i high)确保返回的索引不会越界。2.2 Hoare 双边扫描工程里更常见、坑也更多Lomuto 虽然好写但扫描时它只从单边推进每次交换通常只把一个元素放到最终位置常数较大。Hoare 分区则是从左右两边同时向中间扫描交换次数更少也是很多教科书和工程代码的默认方案。int partition(int arr[], int low, int high) { int pivot arr[low (high - low) / 2]; int i low - 1; int j high 1; while (1) { do { i; } while (arr[i] pivot); do { j--; } while (arr[j] pivot); if (i j) { return j; } swap(arr[i], arr[j]); } }注意递归的区间必须写成[low, j]和[j 1, high]这是 Hoare 版本和 Lomuto 最大的区别。因为 Hoare 返回的 j 并不保证指向基准元素的最终位置它只是“左半边边界”。如果照搬 Lomuto 的quickSort(arr, low, p - 1)和quickSort(arr, p 1, high)在i ! j的时候还能碰巧通过一旦i j就会出现high不变、low也不变的死循环最终栈溢出。还有一个常见的坑do...while里用的比较是严格和严格目的是让等于 pivot 的元素留在两边被交换从而把重复元素尽量均匀地分到左右。如果你改成和虽然逻辑上看起来没错但两个指针会在遇到大量相等元素时冲出数组边界直接访问非法内存。这个坑我年轻时在线上程序里踩过一次数组元素全是同一个值时程序直接崩了排查了半天才意识到是比较符号的问题。Hoare 分区的平均交换次数大约是 Lomuto 的三分之一数据规模越大优势越明显。所以如果你要写一个性能更好的手写快排优先考虑 Hoare。2.3 不同语言实现时的细节差异同样是“数组排序”不同语言里数组的语义其实完全不同直接照着别的语言的写法抄很容易出问题。Java 的数组是对象int[]和Integer[]的排序方法不一样。Arrays.sort(int[])底层用的是双轴快排Arrays.sort(Object[])用的是 TimSort归并的优化版因为对象排序通常要求稳定。如果你自己手写快排处理Integer[]要注意交换引用和交换基本类型在性能上没有本质区别但 null 元素会直接让compareTo抛空指针。Python 的list是动态数组切片arr[:]是浅拷贝得到的是新列表和 Java 数组直接赋值传引用完全不同。用 Python 写快排时如果你在分区里写left [x for x in arr if x pivot]这种方式那是归并思路不是快排思路快排要求原地交换。真要在 Python 里原地排序直接调用list.sort()或者使用sorted()其实是最优解纯手写快排在 Python 里反而因为动态类型和函数调用开销跑得很慢。C# 里要提一个很经典的疑问不同的 class 可以组成数组吗答案是可以。只要它们有一个公共的基类或者共同实现的接口比如都继承自object就能放进同一个数组但这个数组的静态类型是基类类型。排序的时候问题就来了Array.Sort默认用IComparable如果基类没实现这个接口就必须传一个ComparisonT委托或者实现IComparerT接口。我处理这类需求时通常直接在派生类里各自实现CompareTo但写上转型逻辑否则两个不同类型的对象比较起来语义混乱。对象数组排序的核心始终只有一个比较器必须明确告诉排序算法“谁在前、谁在后”。3. 数组排序中绕不开的优化点从能跑到跑得快3.1 枢轴选择的三个层次固定、随机、三数取中基础的 Lomuto 和 Hoare 版本通常直接选第一个或最后一个元素当枢轴这在数据完全随机的时候没什么问题但遇到有序数组或者逆序数组就麻烦了每次分区只能把一个元素放到正确位置递归深度变成 n时间复杂度退化成 O(n²)。实践里我测试过一个 10 万个已排序整数的数组固定选最后一个元素做枢轴的 Lomuto 版本跑了足足几秒而同规模随机数据只花几十毫秒差距就是这么夸张。解决办法第一层是随机选枢轴。在low和high之间随机选一个下标先和最后一个元素交换再走固定枢轴的逻辑。这样做的好处是从概率上保证了最坏情况几乎不会出现坏处是随机数生成有额外开销而且对于“恰好有一小部分有序”的数据收益并不明显。第二层是三数取中。取区间首、中、尾三个位置的元素排序后取中间值作为枢轴。因为真实数据往往不是完全无序而是接近有序首中尾三个数的中位数能很好地代表整个区间的“中间水平”避免选到极端值。实现也很简单private static int medianOfThree(int[] arr, int low, int high) { int mid low (high - low) / 2; if (arr[mid] arr[low]) swap(arr, low, mid); if (arr[high] arr[low]) swap(arr, low, high); if (arr[high] arr[mid]) swap(arr, mid, high); swap(arr, mid, high - 1); return arr[high - 1]; }这里我习惯把中位数放到high - 1的位置这样真正的最后一个元素arr[high]作为哨兵在 Hoare 分区时能避免边界判断的很多麻烦。JDK 里的Arrays.sort底层做得更极端用的是双轴快排取五个元素作为候选再选枢轴但那个复杂度对于手写场景就有点过了。实际项目里三数取中已经能解决绝大多数退化问题。3.2 小数组切换插入排序节省递归开销快速排序是递归算法递归调用有函数调用开销分区本身也有常数开销。当区间规模缩小到一定阈值以下时继续递归反而不划算直接改用插入排序更高效。这个阈值一般在 10 到 47 之间JDK 里用的阈是 47我自己的习惯是 16。实现方式是在quickSort开头加一个判断private static final int THRESHOLD 16; public static void quickSort(int[] arr, int low, int high) { if (high - low 1 THRESHOLD) { insertionSort(arr, low, high); return; } int p partition(arr, low, high); quickSort(arr, low, p - 1); quickSort(arr, p 1, high); }为什么要选插入排序而不是选择排序因为插入排序在数据接近有序时几乎能达到 O(n)它利用的是“前一段已经排好序”的特性而选择排序无论数据顺序如何都要比较约 n²/2 次常数固定且无法提前终止。切到插入排序后整个快排的递归深度也会降低因为底层的小区间不再继续分裂这对防止栈溢出也有帮助。3.3 重复元素多怎么办三分区才是真的救星经典快排在元素全相等或者只有少数几种取值时会反复把相等元素放到枢轴两边导致递归区间缩水很慢性能灾难性地退化。比如对一个全是 0 和 1 的二进制数组排序普通快排会做大量无意义交换效率甚至不如简单计数。解决办法是三分区三路快排思路仍然是选一个枢轴但把数组分成小于枢轴、等于枢轴、大于枢轴三段。递归时只处理小于段和大于段等于段直接跳过。private static void quickSort3Way(int[] arr, int low, int high) { if (high low) return; int lt low; int gt high; int i low 1; int pivot arr[low]; 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, low, lt - 1); quickSort3Way(arr, gt 1, high); }这里lt维护“小于枢轴区”的右边界gt维护“大于枢轴区”的左边界。遇到小于枢轴的元素把它换到左边lt和i同时前进遇到大于枢轴的元素把它换到右边gt后退但i不动因为换过来的元素还没有被检查遇到相等的元素直接i。这个写法一定要手工跑一遍否则很容易在gt后退时漏掉对换过来元素的处理。我用三路快排排过一组包含 70% 重复值的日志时间戳数组耗时只有普通快排的十分之一左右。对于真实业务里那些“取值种类不多但数据量巨大”的数组三路快排几乎是保命级别的优化。4. 关于数组的各种坑指针、多维、切片与越界4.1 指针数组排序时到底该比什么在 C 和 C 里int* arr[10]是一个指针数组每个元素都是int*类型。如果直接对指针数组做快排比较的是指针本身的数值也就是地址大小而不是指针指向的内容。结果就是把一堆内存地址排了个序看起来是“排好了”但完全不是你要的业务顺序而且程序还可能因为访问了无效地址直接崩溃。正确做法是分两层看如果数组里存的是字符串指针比如char* strArr[]比较时要调用strcmp而不是如果存的是结构体指针要按结构体里的某个字段比较。C 标准库的qsort能处理这个问题正是因为它的第四个参数是函数指针int (*compar)(const void*, const void*)比较规则完全由你决定。int compareStr(const void* a, const void* b) { return strcmp(*(const char**)a, *(const char**)b); }这里的*(const char**)a是新手最容易懵的地方a是指向数组元素的指针而数组元素本身是指针所以a是指向指针的指针需要先解引用一层才能拿到char*。把这两层关系理清了指针数组排序的基本功才算过关。数组指针int (*arr)[N]和指针数组正好相反它是指向“一个长度为 N 的整型数组”的指针常用于二维数组的行操作。要对这种结构排序得先明确“按行里的哪个维度排序”然后写对应的比较逻辑。这个方向考研和面试都喜欢考但实际项目里用到的频率远不如指针数组重点还是要把两者区分清楚。4.2 多维数组、切片与动态数组的排序场景Python 的 numpy 数组和原生 list 不是一回事。numpy 里np.sort(arr)返回一个排好序的新数组不改原数组arr.sort()则是原地排序直接修改原数组。更隐蔽的是多维数组用切片取出子数组时是“视图”不是“拷贝”修改切片会同步影响原数组。比如你要对二维数组的某一列排序先col arr[:, 1]然后col.sort()你会发现原数组的第二列也跟着变了。如果要保留原数组必须用np.sort(col)或者col.copy()之后再做排序。普通 Python list 的切片arr[:]反而是真正的拷贝和 numpy 的视图语义完全不同。这个差异如果不注意会在数据预处理的时候给你整出各种莫名其妙的结果。我在处理 CSV 数据时就吃过这个亏用 numpy 读进来想着对“排序后的某列做分析”结果改了临时变量原 DataFrame 也跟着变了整个分析流程全乱。C 的std::vector是动态数组底层是连续内存但它扩容时会把旧数据整体拷贝到新内存原来的指针和迭代器全部失效。你用快排对 vector 排序时如果提前保存了一个迭代器扩容后它指向的位置已经不属于这个容器再访问就是未定义行为。所以写了std::sort(v.begin(), v.end())就不要再持有之前的旧迭代器做任何操作。4.3 数组越界与递归深度的排查思路快排写崩十有八九是数组越界和递归死循环。越界的典型场景是 Hoare 分区的do...while指针移出[low, high]范围。前面提过比较符号写错是原因之一另外一个隐蔽原因是枢轴值根本不存在于当前区间内导致两个指针都以同一个方向越过边界循环永远结束不了。遇到这种问题我的排查习惯是在分区入口打印low、high、枢轴值和分区后的数组状态before: low2, high8, pivotarr[5]4 after: low2, high8, pivotIndex3, arr[1,2,3,4,5,9,7,8,6]如果打印结果显示返回的分区索引和low相等同时下一层递归还是同样的区间就说明分区失败问题基本锁定在比较符号或者while(1)的退出条件上。另一个高频崩溃是递归深度过深导致栈溢出。建议用尾递归优化每次都只递归较短的一半较长的一半循环处理public static void quickSort(int[] arr, int low, int high) { while (low high) { int p partition(arr, low, high); if (p - low high - p) { quickSort(arr, low, p - 1); low p 1; } else { quickSort(arr, p 1, high); high p - 1; } } }这样做能让递归栈深度变成 O(log n)即使数据规模到百万级别也不会爆栈。这个技巧面试时讲出来非常加分因为它展示了你对“递归深度”这个隐形成本的真正理解。5. 性能对比与场景选择5.1 快排、归并、堆排序到底怎么选数组排序的世界里不只快排一个答案选哪种排序要看数据特性和硬件约束。我整理了一个常用对比表排序算法平均时间复杂度最坏时间复杂度额外空间稳定性适用场景快速排序O(n log n)O(n²)O(log n)不稳定一般数组性能优先归并排序O(n log n)O(n log n)O(n)稳定对象数组要求稳定堆排序O(n log n)O(n log n)O(1)不稳定内存受限无法递归快速排序在平均情况下常数最小因为它对内存的访问是顺序扫描对缓存极其友好。归并排序稳定但需要额外 O(n) 空间数据量大的时候内存占用明显。堆排序虽然最坏也是 O(n log n) 且只用 O(1) 空间但它的访问模式是跳跃式的缓存命中率差实际跑起来常数很大通常不是第一选择。JDK 的Arrays.sort和 C 的std::sort都是混合策略数据量小时用插入排序数据量大时用快排检测到递归过深时切堆排序检测到大量重复用三路快排。这基本就是工程排序的完全体形态。5.2 判断“这次该不该用快排”的几条经验结合实际工作经验我一般按下面几条来判断数据规模小于 50直接用插入排序省去递归开销。数据接近有序用 TimSort 风格或快排加三数取中加阈值切换都比朴素快排稳。要求稳定输出也就是说相等元素的相对顺序不能变那快排直接出局用归并或 TimSort。内存极其紧张栈空间也小比如嵌入式环境考虑堆排序。普通业务场景直接调标准库排序不要重复造轮子。标准库的排序实现经过了无数优化手写版本很难在综合性能上超过它。我见过太多人为了“展示自己会写快排”在业务代码里手写一个朴素快排结果数据稍微有序一点就直接退化线上延迟飙高。排序这事儿先理解原理再懂得选型最后才是亲手实现。最后说说我自己的体会我最早手写快排时Lomuto 版本总是把j high写成j high结果每次分区后基准的位置都是错的数组排完序里还有乱序。后来我养成一个笨办法不管写哪个版本先拿 5 个元素的数组在纸上把每一趟分区的状态画出来再对照代码逐行走。这个方法帮我抓出了无数边界问题也比直接看别人的总结有效得多。快排的真正难点从来不是背下那几行代码而是你能不能在脑子里模拟出指针一步步移动、数组一次次交换的过程。把这一步做扎实了再去看三路快排、双轴快排、尾递归优化都是一层窗户纸的事。