企业官网建设流程全解析

1. 快速排序到底在排什么

1.1 从“分而治之”说起

如果你用 JavaScript 写过一段时间的业务代码，肯定没少跟排序打交道。表格要按时间倒序、排行榜要按分数降序、下拉选项要按首字母排列——这些场景里，最省事的方案是直接调用Array.prototype.sort。但一旦你打开排序算法的大门，绕不开的第一个重量级选手就是快速排序（Quick Sort）。

快速排序的定位很明确：它是一类基于比较的排序算法，核心策略是“分而治之”（Divide and Conquer）。这和冒泡排序那种“我跟你比、你跟它比”的挨个交换思路完全不一样。快速排序的思路更像是一个管理者在拆解任务：先把大问题拆成两个小问题，分别解决，再把结果合并起来。只不过，它的“拆”不是凭空拆，而是通过一个叫“基准值”的锚点，把数组分成“小于基准值”和“大于基准值”两拨，然后对这两拨递归执行同样的操作。

很多人会觉得快速排序是教科书里的东西，实际用不到。但在 JS 世界里，sort方法的底层实现（各引擎不同）在数组规模较大时，通常会选择快速排序的变种或者混合策略。也就是说，你每天都在用的原生排序，骨子里可能就有快排的影子。

1.2 快速排序的核心三个动作

把快速排序拆到最细，其实只有三个反复执行的动作：

• 选一个基准值（pivot）。
• 把数组分区（partition）：让比基准值小的元素跑到基准值左边，比基准值大的元素跑到右边，相等的元素放哪边要看具体实现习惯。
• 对左右两个分区分别递归执行上述操作。

递归的终止条件是：子数组的长度小于等于 1。这时候没有东西需要排序，直接返回。

这三个动作里，基准值的选取和分区的方式直接决定了快排的性能。如果基准值选得特别“偏”，比如每次正好选到数组的最大值或最小值，那分区的结果就是一边空空如也，另一边塞满所有元素。这种极端情况会让快速排序的时间复杂度跌到 O(n²)，跟冒泡排序一个水平线。所以，不要小看“选基准值”这个动作，它是快排性能的命门。

1.3 基准值：快速排序的灵魂

基准值是什么？你可以把它理解成一个“分界线标准”。比如有一排身高参差不齐的人，你随手拉一个人出来当标准：比他矮的站左边，比他高的站右边。这个被拉出来的人就是基准值。第二轮，左边的人群里再拉一个基准值继续分，右边也一样。最终每个人都会找到自己的位置。

在代码里，基准值通常取数组的某个元素。最简单的取法是：

const pivot = arr[arr.length - 1];

也就是拿最后一个元素当基准。这种写法最好理解和实现，但碰上已经有序的数组，就会非常尴尬。举个例子：对[1, 2, 3, 4, 5]排序，每次拿最后一个元素当基准，那最后一次元素5就是最大值，分区后左边是[1, 2, 3, 4]，右边是空的。下一轮再拿4当基准，又是左边一堆、右边空。每一轮只排掉一个元素，递归深度接近 n，性能直接崩。

所以，基准值的选法从“最后一个元素”到“随机选一个”再到“取左中右三个数的中位数”，每一种方案的背后，都是对最坏情况的预防。后面我会专门讲优化策略，这里先记住：基准值的选择不是无关紧要的代码习惯，而是快排性能的关键变量。

2. 用 JS 实现第一版快速排序

2.1 最容易理解的“额外数组”版本

先不要急着上最优解。我建议写快排时，第一步先写一个“能工作但不够高效”的版本，把思路理清楚。这个版本使用额外的数组来存放分区结果，代码非常友好：

function quickSort(arr) { if (arr.length <= 1) { return arr; } const pivot = arr[arr.length - 1]; const left = []; const right = []; for (let i = 0; i < arr.length - 1; i++) { if (arr[i] < pivot) { left.push(arr[i]); } else { right.push(arr[i]); } } return [...quickSort(left), pivot, ...quickSort(right)]; }

这段代码只有三块逻辑：判断递归出口、把除基准外的元素分到 left 或 right、拼接递归结果。

你可以拿[5, 2, 8, 1, 9]代入走一下。第一次分区，基准是9，所有元素都比它小，所以 left 是[5, 2, 8, 1]，right 是空数组。接着对 left 继续快排，基准是1，left 为空，right 是[5, 2, 8]。递归下去，最终能拿到[1, 2, 5, 8, 9]。

2.2 这个版本有什么问题

这个版本非常适合学习和演示，但放到真实业务中，有两个明显的问题。

第一个问题是空间浪费。每次分区都要新建两个数组，把一个长度为 n 的数组拆成两个子数组的同时，额外占用 O(n) 的内存。递归的每一层都这么干，总空间复杂度会达到 O(n log n) 甚至更多。对于小数组无所谓，但对几万、几十万条数据的排序，内存消耗会非常难看。

第二个问题是稳定性与相等元素处理。我在上面用arr[i] < pivot判断，相等的元素被放进了 right。这保证了相等的元素不会跑到基准左边去，但如果你把条件写成<=，那相等的元素就会跑到 left 里。两种写法都不会破坏排序正确性，但会影响“稳定性”。更重要的是，这个版本没有做到“原地排序”（In-place），它和真正高效的快排之间差了一次脱胎换骨。

2.3 小规模测试送分题

写完后，建议你用几组边界数据验证一下：

• 空数组[]
• 只有一个元素的数组[1]
• 已经有序的数组[1, 2, 3, 4, 5]
• 全部相等的数组[3, 3, 3, 3]
• 包含负数和零的数组[-3, 0, -1, 5, 2]

这组测试在任何排序算法实现后都值得跑一遍。快排的递归基线和分区条件如果写错，在“空数组”或“全部相等”这类边界条件下最容易暴露。

3. 原地分区：真正能用的快速排序

3.1 经典 Lomuto 分区方案

想要避免额外的数组开销，就得在一个数组里通过交换元素完成分区。Lomuto 分区方案是最好写的一种原地分区方式，它的思路是维护一个“已处理区域”的边界索引。

function partition(arr, low, high) { const pivot = arr[high]; let i = low - 1; for (let j = low; j < high; j++) { if (arr[j] < pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; } } [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; return i + 1; } function quickSortInPlace(arr, low = 0, high = arr.length - 1) { if (low < high) { const pivotIndex = partition(arr, low, high); quickSortInPlace(arr, low, pivotIndex - 1); quickSortInPlace(arr, pivotIndex + 1, high); } return arr; }

这段代码是面试里非常常见的写法。partition函数里，i指向“最后一个小于基准值的元素的位置”，j负责遍历。每当发现一个小于基准值的元素，就把i前移，然后交换arr[i]和arr[j]。遍历结束后，把基准值放到i + 1的位置。

你可以把i想象成一个“慢指针”，它只在遇到小于基准值的元素时才移动。j是“快指针”，不管元素大小，都得一路扫过去。快慢指针之间的区域，就是已经确认“大于等于基准值”的部分。

3.2 Hoare 分区方案与对比

Lomuto 分区简洁，但它的交换次数通常比 Hoare 分区多。Hoare 是快速排序发明者提出的原始方案，它的思路是从数组两端同时向中间扫描：左指针找大于基准值的元素，右指针找小于基准值的元素，找到后交换。

function partitionHoare(arr, low, high) { const pivot = arr[Math.floor((low + high) / 2)]; let i = low - 1; let j = high + 1; while (true) { do { i++; } while (arr[i] < pivot); do { j--; } while (arr[j] > pivot); if (i >= j) { return j; } [arr[i], arr[j]] = [arr[j], arr[i]]; } }

Hoare 分区最终返回的j，不是基准值的最终位置，而是“左半区的结尾索引”。递归时要注意，左区间是[low, j]，右区间是[j + 1, high]，这和 Lomuto 的递归边界不一样，写错了会死循环或漏排。

对比二者的特点：

我个人的经验是：面试或写业务工具时，Lomuto 足够用；如果你对性能比较敏感，或者要处理超大规模数据，可以试试 Hoare。但无论用哪种，都要先画一张小数组的交换过程图，把边界搞明白再上代码。

3.3 原地版本的递归实现

原地版本的核心方法签名是quickSortInPlace(arr, low, high)。很多人刚接触时会有个疑问：为什么非要传low和high？直接在函数内部用arr.slice()不行吗？

因为slice会复制数组，一旦复制就失去了“原地”的意义。原地排序想要的是：在原始数组的内存空间里通过交换调整顺序，最终只返回这个数组本身。通过low和high控制当前处理区间，就能避免创建子数组。

递归的基线条件是low >= high。也就是说，当区间里没有元素或只有一个元素时，不用再做任何事。注意不要写反，写成if (low === high) return;就会漏掉low > high的情况（比如分区后左区间为[low, pivotIndex - 1]，如果pivotIndex === low，那左区间就是[low, low - 1]，是无效区间）。

4. 复杂度、稳定性与隐藏陷阱

4.1 时间复杂度为什么是 O(n log n)

快速排序的平均时间复杂度是 O(n log n)。这个结论怎么来的？可以用一个简单模型理解。

每一轮分区，我们要遍历当前区间的所有元素，这个操作的耗时是 O(n)（n 是当前区间长度）。如果基准值每次都把数组分成两个差不多的部分，那递归的深度就是 log₂n 层。O(n) 乘以 O(log n)，就是 O(n log n)。

用生活化的例子：一本 1000 页的书，你要按页码整理。每轮分区相当于把书从中间翻开，把前半部分和后半部分分开整理。每次都能对半分开，那只需要 log₂(1000) ≈ 10 轮。每轮翻书的动作和页数成正比。这就是快排高效的本质：它利用了递归树的平衡性。

4.2 什么情况下会退化到 O(n²)

当基准值每次都是当前区间的最小值或最大值时，分区后一边是空的，另一边是 n-1 个元素。递归树变成一根“斜线”，深度从 log n 变成 n。每一层仍然要遍历 O(n) 个元素，总耗时 O(n²)。

最容易触发这种退化的场景有三个：

• 数组已经有序（升序或降序），而基准值固定取第一个或最后一个元素。
• 数组元素全部相等，且基准值取某个固定位置。
• 数组中存在大量重复值，且分区逻辑没有对相等元素做特殊处理。

所以，快排的最坏情况不是理论虚构，日常开发中就可能遇到。一个按时间倒序排列的列表，如果你恰好每次取第一个元素当基准，排序它就是在挑战 O(n²)。

4.3 稳定性和内存开销

快速排序是不稳定的排序算法。这是面试高频考点，也容易让人疑惑：“不稳定是什么意思？”

稳定性指的是：如果两个元素值相等，排序后它们的相对顺序保持不变。举个例子，有一组学生数据，先按学号排好序，再按成绩排序。稳定排序会保留相同成绩学生之间原有的学号顺序，不稳定排序则可能打乱它。

快速排序为什么不稳定？因为在分区过程中，我们通过交换来移动元素。交换本身就很容易让相等的元素越过彼此。比如 Lomuto 分区里，i指针区域的元素和j指针指向的小于基准值的元素交换时，如果两个值相等，相对顺序就可能发生变化。

那有什么办法吗？标准的快排无法保证稳定性。如果业务里对稳定性有硬性要求（比如多关键字排序），应该选择归并排序，或者给每个元素额外记录一个原始索引，用索引做次级比较。这种“带索引的包装对象”方案虽然能补救，但会牺牲空间和简洁性，需不需要用，取决于实际场景。

4.4 内存开销的真相

原地快排的空间复杂度不是 O(1)，而是 O(log n)。这是因为递归调用需要占用函数调用栈空间。每次递归调用都要保存当前函数执行的上下文，递归深度就是栈的最大深度。

平均情况下递归深度是 O(log n)，所以空间复杂度 O(log n)。最坏情况下递归深度是 O(n)，空间复杂度退化到 O(n)。如果你在浏览器里用一个很大的有序数组调快排，还可能直接触发RangeError: Maximum call stack size exceeded，也就是栈溢出。

因此，快排并不是完全不占内存的算法，只是相比归并排序（需要 O(n) 的额外数组）要省得多。这也是它在很多语言标准库里作为主力排序算法的原因之一。

5. 工程级优化：让快速排序更实用

5.1 基准值选择：三数取中

上面反复提到了最坏情况。工程上最常用、也最容易实现的优化之一，是“三数取中”（Median-of-Three）。

做法很简单：在当前区间[low, high]里，取左端、右端和中间位置三个元素，比较它们的大小，把中间值作为基准值。

function getPivotIndex(arr, low, high) { const mid = Math.floor((low + high) / 2); if (arr[low] > arr[mid]) { [arr[low], arr[mid]] = [arr[mid], arr[low]]; } if (arr[low] > arr[high]) { [arr[low], arr[high]] = [arr[high], arr[low]]; } if (arr[mid] > arr[high]) { [arr[mid], arr[high]] = [arr[high], arr[mid]]; } return mid; }

这个函数做了三件事：把三个位置的元素按序排列，使得arr[low] <= arr[mid] <= arr[high]，然后返回mid作为基准索引。这样选出来的基准值，至少能保证不是当前区间的极端值。对于“几乎有序”的数组，三数取中效果显著，能避免退化成 O(n²)。

注意一点：三数取中本身也有开销，所以并不是每个小区间都要用。通常当区间长度大于某个阈值（比如 10 或 20）时才启用，小区间直接另作处理。

5.2 小区间插入排序

递归到小区间时，比如区间长度小于 10，快速排序的优势就变小了。递归带来的函数调用开销反而比插入排序的直接比较交换更昂贵。插入排序有个特点：对于“近乎有序”的小数组，效率极高。

所以一种经典的混合策略是：在快排的递归过程中，如果区间长度小于某个阈值（常见为 10），就改用插入排序，不再继续递归。

function insertionSort(arr, low, high) { for (let i = low + 1; i <= high; i++) { const temp = arr[i]; let j = i - 1; while (j >= low && arr[j] > temp) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = temp; } }

然后在快速排序里加一个判断：

function quickSortOptimized(arr, low = 0, high = arr.length - 1) { if (low >= high) { return; } if (high - low <= 10) { insertionSort(arr, low, high); return; } const pivotIndex = partition(arr, low, high); quickSortOptimized(arr, low, pivotIndex - 1); quickSortOptimized(arr, pivotIndex + 1, high); }

我试过这个优化，在数据规模 10 万以上时，能明显感受到整体耗时的降低。阈值的具体值不是固定的，10 到 20 之间都合理。你也可以根据实际数据做一点调整，但没必要调到太极端。

5.3 尾递归优化

递归的一大隐患是栈深度。快排的递归可以写成尾递归形式，减少一部分栈空间压力。什么是尾递归？简单说，就是递归调用是函数中“最后一步执行的操作”。在快排中，我们可以先递归处理较短的那一半，再递归处理较长的那一半，通过这种方式控制递归深度。

function quickSortTailRecursive(arr, low, high) { while (low < high) { const pivotIndex = partition(arr, low, high); if (pivotIndex - low < high - pivotIndex) { quickSortTailRecursive(arr, low, pivotIndex - 1); low = pivotIndex + 1; } else { quickSortTailRecursive(arr, pivotIndex + 1, high); high = pivotIndex - 1; } } }

这里的思路很巧妙：每次递归只处理较小的一侧，较大的一侧通过循环继续下一轮处理。这样递归深度被限制在 O(log n) 级别，即使数据规模很大，也不容易把调用栈撑爆。

不过要注意，JavaScript 引擎当前对“尾递归”的支持并不统一，不是所有环境都做尾调用优化。所以这段代码真正的价值在于“减少递归深度”的逻辑，而不是依赖引擎优化。即便如此，它也能在很大程度规避栈溢出问题，值得作为优化项掌握。

5.4 处理大量重复元素：三路划分

如果数组里有大量重复元素，比如[2, 1, 2, 2, 3, 2, 2]，普通快排会在分区时把所有等于基准值的元素都分到某一边，导致两边大小极度不平衡。三路划分（3-Way Partition）专门解决这个问题。

它的思想是：把数组分成三个区域——小于基准值的、等于基准值的、大于基准值的。这样，所有等于基准值的元素一次性就位，不需要再参与后续递归。

下面是一个基于三路划分的快排实现：

function quickSort3Way(arr, low, high) { if (low >= high) { return; } const pivot = arr[low]; let lt = low; // 小于基准的边界 let i = low + 1; // 当前遍历位置 let gt = high; // 大于基准的边界 while (i <= gt) { if (arr[i] < pivot) { [arr[lt], arr[i]] = [arr[i], arr[lt]]; lt++; i++; } else if (arr[i] > pivot) { [arr[i], arr[gt]] = [arr[gt], arr[i]]; gt--; } else { i++; } } quickSort3Way(arr, low, lt - 1); quickSort3Way(arr, gt + 1, high); }

这段代码用三个指针协作：lt指向“小于区”的下一个位置，gt指向“大于区”的上一个位置，i负责遍历中间区域。遇到小于基准的元素，就把它换到左边；遇到大于基准的元素，就把它换到右边；相等的元素直接继续前进。

我在给某电商平台做数据处理时遇到过几十万级的大量重复评分数据，普通快排要跑几百毫秒，换成三路划分后，耗时降到了几十毫秒级别。如果你处理的业务数据中重复值很多（比如状态码、星级、类别 ID），三路划分是非常值得掌握的方案。

5.5 综合实现示例

把这些优化组合起来，可以得到一个相对完整的工程级实现。下面给出一份可以拿去用的版本：

function insertionSort(arr, low, high) { for (let i = low + 1; i <= high; i++) { const key = arr[i]; let j = i - 1; while (j >= low && arr[j] > key) { arr[j + 1] = arr[j]; j--; } arr[j + 1] = key; } } function medianOfThree(arr, low, high) { const mid = low + ((high - low) >> 1); if (arr[low] > arr[mid]) [arr[low], arr[mid]] = [arr[mid], arr[low]]; if (arr[low] > arr[high]) [arr[low], arr[high]] = [arr[high], arr[low]]; if (arr[mid] > arr[high]) [arr[mid], arr[high]] = [arr[high], arr[mid]]; return mid; } function partition(arr, low, high) { const pivotIndex = medianOfThree(arr, low, high); const pivot = arr[pivotIndex]; [arr[pivotIndex], arr[high]] = [arr[high], arr[pivotIndex]]; let i = low - 1; for (let j = low; j < high; j++) { if (arr[j] < pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; } } [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; return i + 1; } function quickSortEngineered(arr, low = 0, high = arr.length - 1) { while (low < high) { if (high - low <= 10) { insertionSort(arr, low, high); break; } const pivotIndex = partition(arr, low, high); if (pivotIndex - low < high - pivotIndex) { quickSortEngineered(arr, low, pivotIndex - 1); low = pivotIndex + 1; } else { quickSortEngineered(arr, pivotIndex + 1, high); high = pivotIndex - 1; } } return arr; }

这份实现结合了三数取中、插入排序和尾递归控制的思路。它虽然不可能成为性能之王，但在绝大多数业务场景下，表现已经足够稳定，而且不容易踩到栈溢出的坑。

6. 常见问题与排查技巧

6.1 递归爆栈

最常遇到的问题就是Maximum call stack size exceeded。触发原因通常是递归深度过大。排查方向有三个：

• 数据规模本来就很大（比如超过 10 万），且没有做任何尾递归控制。
• 数组基本有序，而基准值固定取第一个或最后一个元素，导致分区严重不平衡。
• 系统调用栈比较小，比如某些浏览器环境对栈深度限制更严格。

解决方案优先推荐“三数取中 + 小区间插入 + 小侧优先递归”的组合，还可以把递归改成迭代版本。如果数据真的超级大，其实应该考虑是否一定要用纯前端排序，改用分批处理或服务端排序会更合理。

6.2 排序结果不对或丢失元素

这类问题几乎都出在分区逻辑的边界条件上。常见错误有：

• Lomuto 分区返回i而不是i + 1，导致基准位置没放对。
• Hoare 分区递归边界写错，左右区间重叠或遗漏。
• 递归基线条件写反，导致无限递归或直接跳过未处理的区间。

调试这类问题有一个非常实用的办法：找一个只有 5 个元素的小数组，在每次交换后打印数组内容，手动跟踪一轮分区的过程。或者用console.assert验证分区后的不变量：基准左边的元素都小于等于基准，右边的元素都大于等于基准。

6.3 性能测试怎么对比

想验证优化是否有用，别靠感觉。我常用的一种测量方式是：准备随机数组、有序数组、接近有序的数组、大量重复元素的数组，分别用不同版本排序，记录耗时。

const data = Array.from({ length: 100000 }, () => Math.random() * 10000); console.time('quickSortInPlace'); quickSortInPlace([...data]); console.timeEnd('quickSortInPlace'); console.time('quickSortEngineered'); quickSortEngineered([...data]); console.timeEnd('quickSortEngineered');

注意每次排序都要用[...data]复制一份，否则第一次排序会把原数组改掉，第二次测的就是排好序的数组，结果就失真了。console.time的精度够用，但如果要更严谨，可以使用performance.now()。

从我的测试结果看，随机数组上，优化版不一定比简单版快太多，但在有序数组和大量重复元素数组上，优化版的优势非常明显，有时能有数倍甚至超过十倍的差距。

6.4 快速排序与原生 sort 的取舍

很多人会有这个疑问：既然原生sort已经很好用，为什么还要自己写快排？

答案是：大多数时候，直接用sort就够了。原生排序由引擎底层实现，会根据数组长度和元素类型选择策略，性能通常比自己写的 JS 排序更快。但它也有局限：

• 不同引擎的排序算法实现不同，行为不完全一致。
• 如果需要对对象数组按某个字段排序，每次比较都涉及函数调用，性能可能不如预先提取字段后排序。
• 面试和学习场景中，快速排序的思想和实现是绕不开的基础技能。

我个人的看法是：业务代码里，优先使用sort，除非你遇到了明确的性能瓶颈，或者需要自定义排序逻辑。而学习排序算法，重点在于理解分治思想、递归写法、指针操作和复杂度推导，这些能力会让你在读别人代码、排查性能问题、设计数据流程时更得心应手。

回过头看，快速排序之所以被称为经典，并不只是因为快，而是因为它把“分而治之”这个思想用到了极致。从最简单的额外数组版本，到原地分区，再到三数取中、三路划分和尾递归控制，每一步优化都对应着一种现实中的性能痛点。我在项目里用过很多次快速排序，也帮别人查过不少排序相关的诡异问题，最常见的根源其实就两个：基准值选得太随意，或者对相等元素的处理想当然。如果你能把分区过程的每一步交换都在纸上画清楚，快排对你来说就不会再有任何黑魔法。