Skip to main content

1 / 4概念

Sorting & Searching

排序把无序输入变成全序,查找再利用这个全序把候选集砍半。判断标准不是“哪个排序最快”,而是数据规模、比较代价、稳定性、内存和输入分布。

1 概念​

1.1 一句话定义​

排序把 n 个元素按给定比较关系排成非降或非升序列;查找在给定结构中定位满足条件的元素。两者共享同一个前提:元素之间必须存在可比较的全序。

1.2 它解决什么问题​

  • 输出有序:报表、分页、合并、去重、top-k 都依赖顺序。
  • 查找加速:有序数组二分是 O(log n),无序线性扫描是 O(n)。
  • 算法前置:扫描线、区间合并、双指针、并查集预处理都要求先排序。

没有排序,这些场景只能退化为嵌套扫描;没有查找结构,每次查询都要重新遍历。

1.3 不属于本页的内容​

主题去哪
渐进分析与复杂度记号Complexity Analysis
堆、平衡树、哈希表Trees & Heaps、Linear Structures
图的最短路与最小生成树Graph Algorithms
数据库排序、索引与执行计划Indexing & Optimization

1.4 关键术语​

术语含义容易混淆的点
稳定性相等键保持原始相对顺序不是“排序结果是否确定”
原地额外空间 O(1) 或 O(log n)不是“完全不分配内存”
比较模型只能通过 <、=、> 获取信息计数/基数排序不受此限
下界比较排序需要 Ω(n log n) 次比较是模型下界,不是所有排序的下界
在线数据逐个到达时仍能维护有序插入排序在线,快排不在线