排序与查找

是什么，为什么存在

查找会找到满足条件的元素、位置或范围。排序则按一种顺序关系重新排列元素。两者经常配合使用：预先排序可让后续查找具有可预测的对数复杂度，而一次性查找往往根本不需要排序。

商品列表排名、按标识查找请求、从事件中截取时间窗口，以及稳定呈现两条记录时，都会用到这些操作。库函数让语法变得简短，却不会替你选择业务键、处理相同键，也不能证明输入满足查找算法的前置条件。

首先要问的不是「哪个知名算法最快」，而是「数据是什么形态，接下来要对它做什么」。无序数组、数据流、哈希索引和有序数组即使保存相同的逻辑记录，也会提供不同的操作。

线性扫描几乎适用于所有可迭代对象，并且找到匹配项后就能停止。排序需要先收集并比较元素，但会建立一种有序表示，从而支持二分查找、有序输出、分组和范围边界。哈希表更适合反复进行精确键查找，却不会自动提供有序遍历或范围查询。

输入规模和负载同样重要。为了查找一次而排序一万条记录，会增加一次扫描本可避免的工作。如果排序一次后要查找数千次，这项交换就可能合理，前提是查询期间有序表示一直有效。

正确性还取决于具体要什么结果。「查找价格为 1,250 的商品」可能是返回任一匹配商品、第一处匹配位置、最后一处匹配位置，或包含全部匹配项的半开范围。这些是不同契约，键重复时尤其如此。

排序也存在类似歧义。「按优先级排序」没有说明数字较小的是否靠前、同优先级如何排列、比较结果相等的记录是否保留输入顺序，也没有说明能否修改原集合。实现无法从「排序」这个动词中还原这些决策。

这里用数组说明问题，因为随机访问能清楚表现算法差异。同样的原则也适用于数据库索引、搜索服务的倒排列表、有序文件和基于树的集合，但它们的存储与更新成本不同。

工作原理

先看数据形态

数组支持常数时间的索引访问，二分查找因此可以低成本检查中间元素。链表也能保持有序，但反复遍历到中间位置，会消除二分查找通常具有的优势。数据流可能只支持向前读取一次，此时扫描或增量选择算法更自然。

数据形态还包括所有权与新鲜度。有序快照只有在调用方知道它反映了哪些修改时才有用。快照建立后若记录发生变化，在旧顺序中查找可能返回看似合理但实际错误的边界。

应把数据源和为特定任务建立的表示分开。一个数组可以为审计保留到达顺序，另一个数组则保存按价格排序的引用以供范围查找。两种表示可以共享记录对象，而不共享排列顺序。

线性查找不要求有序

线性查找按遇到顺序检查候选项，直到谓词成立或输入结束。对于 n 个元素，它最多执行 n 次谓词检查，因此最坏时间复杂度为 O(n)。只返回一个元素或位置时，额外空间可以保持为 O(1)。

提前停止属于操作契约。查找第一条匹配事件时，应在首次匹配后停止；过滤整个输入会产出所有匹配项，必然继续访问余下元素。如果谓词计算成本很高或数据源是惰性的，混淆两种操作会产生明显代价。

扫描不是需要道歉的退路。面对小型输入、一次查询、持续变化的数据，或者不符合现有顺序的条件时，它往往就是正确算法。它的前置条件很弱：程序只需能够访问每个候选项。

比较函数定义顺序

比较函数（comparator） 把一对元素映射为负数、0 或正数，符号依次表示「左侧靠前」「顺序相等」和「左侧靠后」。返回值的绝对值通常没有意义。

可用的比较函数必须保持一致。元素与自身比较时结果相等；颠倒一对元素时符号随之颠倒；若 a 在 b 前、b 又在 c 前，则 a 必须在 c 前。违反这些性质后，排序过程就没有一个连贯顺序可供生成。

比较结果相等不一定表示对象相等。两张订单可能拥有相同优先级与总额，却有不同标识。 稳定排序（stable sort） 会保留它们在输入中的相对顺序；如果之前的顺序具有业务含义，这项保证就很有价值。

稳定性不会凭空生成缺失的同值排序规则。如果记录来自不保证顺序的数据源，保留这份任意顺序也无法让分页结果可重复。当业务契约需要完整且可重复的顺序时，应增加标识等唯一键作为最后一个排序条件。

排序会改变可用操作

常见的通用比较排序通常需要 O(n log n) 次比较。采用的算法与 API 不同，操作可能分配额外存储，也可能修改输入。这两种行为与比较函数怎样排列值是彼此独立的决策。

排序完成后，相邻值可以分组，边界查找也能隔离范围。当多个后续操作都能利用同一顺序时，预付成本才有意义。如果每次更新都迫使程序完整重排，就要把更新计入负载，不能只考虑查询成本。

增量维护有序数组包含不同量级的成本。二分查找可以在 O(log n) 时间内定位插入位置，但腾出空位可能需要移动 O(n) 个元素。分析一系列操作时，应考虑总成本与 摊还复杂度（amortized complexity） ，不能只看最便宜的一步。

二分查找维持边界

二分查找不只是「看看中间」。它维持一个已知包含答案的区间，检查一个中间元素，再丢弃不可能包含答案的半边。每轮迭代都必须让区间严格缩小。

下界查找会返回键大于或等于目标值的第一个位置。采用半开区间 [low, high) 后，空输入与尾部插入都会自然表示：两个端点都可以等于数组长度。

对于下界，low 之前的位置都已知小于目标值，high 及其后的位置都已知大于或等于目标值。循环在 low === high 时结束；即使没有元素等于目标值，该位置仍然是正确边界。

上界查找会改变相等时的分支规则，返回键大于目标值的第一个位置。因此，与目标相等的元素范围是 [lowerBound, upperBound)。同样的双边界模式也能处理数值区间，不必扫描每条无关记录。

二分查找要求数组、键提取函数与排序时采用的顺序一致。按忽略大小写的规则排序，却用区分大小写的比较来查找，会破坏循环不变量。升序排序后又像处理降序数据那样移动错误端点，也会造成同样问题。

这张图用于辅助决策，不是通用优先级列表。实测负载可能支持另一种表示，内存限制也可能排除某种选择。关键是明确写出前置条件和所有权。

根据操作组合选择

表中列出的是起点，不是自动答案。输入规模、局部性、比较成本、内存、更新频率和所需输出顺序都会改变决策。先建立正确性，再用完整操作组合进行测量。

让结果契约清晰可见

查找函数名应说明它返回的边界或选择结果。lowerBound()、firstOpenTicketForTeam() 和 productsInPriceRange() 都比 find() 更明确，因为调用方能直接看出需要测试哪项承诺。

名称或类型中还应保留单位。整数分、毫秒时间戳和按区域规则比较的标签即使都能放进数组，也需要不同的比较策略。

表示有前置条件时，应把条件放在构建逻辑与测试旁边。只在远处某个调用位置留下注释，无法保护后续每次二分查找，避免它接收过期或顺序不同的数据。

示例

下面的示例从一次扫描开始，再实现稳定的多键排序，最后在有序快照中查找范围。每个文件都用 Node 24.14.0 运行，紧随代码的输出就是进程真实输出。

找到第一个有用结果后停止

工单列表按到达顺序排列，并没有按团队排序。一次团队查找不值得重排集合；返回 undefined 则把缺失情况明确交给调用方。

函数返回 INC-104，因为「第一张」指输入顺序中的第一张。它没有声称会返回时间戳最早或标识最小的工单。如果领域需要其中一种含义，只有谓词还不够，契约必须写明选择规则。

查找不存在的团队会遍历完整数组，然后返回 undefined。如果要在稳定集合中反复执行这种查找，就可以考虑建立从团队到目标工单的映射。这样做会改变更新成本与内存成本，因此它属于表示选择，而不只是局部重写循环。

排名时不修改到达顺序

下一个示例先按优先级数字升序排列订单，再按总额降序排列。toSorted() 会创建新数组，因此原始到达顺序仍可供审计输出使用。

const orders = [
  { id: "A-17", priority: 2, total: 80 },
  { id: "B-04", priority: 1, total: 120 },
  { id: "C-31", priority: 2, total: 50 },
  { id: "D-09", priority: 1, total: 120 },
];

function compareOrders(left, right) {
  const byPriority = left.priority - right.priority;
  if (byPriority !== 0) return byPriority;

  return right.total - left.total;
}

const ranked = orders.toSorted(compareOrders);

console.log(ranked.map((order) => order.id).join(", "));
console.log(orders.map((order) => order.id).join(", "));
console.log(ranked[0].id === "B-04" && ranked[1].id === "D-09");

B-04, D-09, A-17, C-31
A-17, B-04, C-31, D-09
true

B-04 和 D-09 在两个已声明的键上都比较相等。Node 24 遵守 JavaScript 的稳定排序要求，所以它们保留输入顺序。这项保证在本例中足够，是因为到达顺序本身具有意义。

第二行输出确认 orders 没有被重排，但两个数组仍然共享其中的对象引用。toSorted() 复制的是序列，不是每条记录。修改 ranked[0].total 时，通过 orders 观察到的对象也会变化。

查找半开价格范围

最后一个示例以 SKU 作为同价格时的排序条件，建立确定的价格索引。然后用同一个下界函数查找 [minimum, maximum) 的两个端点，因此上限价格有意不包含在结果中。

const products = [
  { sku: "P-40", cents: 1250 },
  { sku: "P-12", cents: 750 },
  { sku: "P-31", cents: 1250 },
  { sku: "P-08", cents: 500 },
  { sku: "P-22", cents: 900 },
];

const byPrice = products.toSorted(
  (left, right) => left.cents - right.cents || left.sku.localeCompare(right.sku),
);

function lowerBound(items, target, keyOf) {
  let low = 0;
  let high = items.length;

  while (low < high) {
    const middle = low + Math.floor((high - low) / 2);
    if (keyOf(items[middle]) < target) low = middle + 1;
    else high = middle;
  }

  return low;
}

function productsInPriceRange(items, minimum, maximum) {
  const start = lowerBound(items, minimum, (product) => product.cents);
  const end = lowerBound(items, maximum, (product) => product.cents);
  return items.slice(start, end);
}

console.log(byPrice.map((product) => `${product.sku}:${product.cents}`).join(", "));
console.log(productsInPriceRange(byPrice, 750, 1250).map((product) => product.sku));
console.log(productsInPriceRange(byPrice, 1250, 1300).map((product) => product.sku));

P-08:500, P-12:750, P-22:900, P-31:1250, P-40:1250
[ 'P-12', 'P-22' ]
[ 'P-31', 'P-40' ]

第一次查询包含价格 750 和 900，却排除 1,250。第二次查询包含价格为 1,250 的两件商品，说明边界查找可以处理重复键，而不必猜测任意精确匹配算法会返回哪个相等元素。

当 minimum === maximum 时，两个边界相同，slice() 返回空数组。当区间位于所有商品之后时，两个边界都等于 items.length。半开区间契约已经定义了这两种情况，不需要特殊分支。

陷阱

使用布尔比较函数

修复方法： 返回负数、0 或正数，并交换参数顺序测试比较函数。需要比较多个键时，应逐键比较，仅当当前结果为 0 时才继续。

忘记默认顺序

修复方法： 对有限数值提供 (a, b) => a - b 这样的显式比较函数。NaN、字段缺失与受区域设置影响的字符串等领域值怎样排列，应另外定义。

查找采用另一套顺序

修复方法： 集中管理键与比较策略，或者提供同时负责构建和查找的有序索引抽象。针对规范化或特殊值改变行为的每处边界，都要测试附近的目标。

把任一重复项当成答案

修复方法： 明确要求下界、上界或相等范围。先定义区间端点是否包含，再测试集合开头、中间和结尾的重复键。

排序时修改共享集合

修复方法： 明确所有权；必须保留源顺序时使用 toSorted()。新数组只是浅拷贝；只有契约还要求独立修改记录时，才需要继续复制记录对象。

为持续过期的索引付费

修复方法： 一起统计构建、查询、插入、删除与失效操作。为派生顺序指定所有者和刷新规则，再用具有代表性的比较成本与数据规模对完整负载进行基准测试。

延伸阅读

• ECMAScript 规范：Array.prototype.sort
• MDN：Array.prototype.sort()
• MDN：Array.prototype.toSorted()
• 《算法》第 4 版：算法分析
• 《算法》第 4 版：快速排序