tech-interview-handbook 排序与搜索专题：复杂度对比、二分查找源码剖析与刷题路线

本文基于 tech-interview-handbook 仓库中的排序与搜索专题速查文档（sorting-searching.md），完整覆盖其核心脉络：各排序算法的时间/空间复杂度对比、语言内置排序算法真相、二分查找及其变体的可运行源码实现、面试中必须识别的两类技巧（有序输入、有限值域），以及必备题与推荐刷题清单。读完后你应能：判断一道题该用二分还是直接调用语言默认排序；默写出无溢出风险的迭代版二分查找与 bisect 变体；并用仓库中自带的可运行参考实现自测。

排序与搜索为什么是同一个专题

排序（Sorting）是将序列中的元素按数值或字典序重新排列的操作，可以是升序也可以是降序。速查文档的开篇就给出了一个关键的面试认知：

一批基础排序算法的时间复杂度是 O(n²)，不应该在面试中使用。在算法面试中，你几乎不需要从零实现任何排序算法。正确做法是用语言内置的排序函数对输入排序，使其可以被二分搜索。

也就是说，面试中排序的定位是"预处理手段"——先把输入排好，再叠加 O(log n) 的二分搜索。对于已排序数组，二分搜索利用其有序性质，将目标值与数组中间元素比较，从而确定目标位于左半还是右半，然后在剩下的半区中继续比较，直到找到目标或区间为空。

各排序算法复杂度总览

原文档给出了完整的复杂度对照表，这是面试中被问"说说常见排序的复杂度"时的标准答案，务必完整掌握：

算法	时间复杂度	空间复杂度
冒泡排序 Bubble sort	O(n²)	O(1)
插入排序 Insertion sort	O(n²)	O(1)
选择排序 Selection sort	O(n²)	O(1)
快速排序 Quicksort	O(n log n)	O(log n)
归并排序 Mergesort	O(n log n)	O(n)
堆排序 Heapsort	O(n log n)	O(1)
计数排序 Counting sort	O(n + k)	O(k)
基数排序 Radix sort	O(nk)	O(n + k)

算法	Big-O
二分搜索 Binary search	O(log n))

两个细节值得注意：Mergesort 的 O(n) 空间来自合并时需要额外数组（可参考后文 mergeSort.js 的实现）；Heapsort 之所以能原地排序，是因为堆可以就地构建在数组上（参考 heap.py）。Counting sort 与 Radix sort 的复杂度依赖 k（值域大小/位数），它们是唯一的非比较排序，这也是后文"有限值域"技巧的理论基础。

面试必知：你语言的默认排序算法到底是什么

原文档特别提醒：必须知道你所用语言默认排序算法的时间和空间复杂度。其时间复杂度几乎肯定是 O(n log n)；如果能说出具体算法名则是加分项。文档给出的事实如下：

• Python 3.11+：默认排序算法是 Powersort，它取代了此前一直使用的 Timsort；
• Java：对象排序使用 Timsort 的实现，基本类型（primitives）排序使用 Dual-Pivot Quicksort（双轴快排）。

这条信息在面试口头表达中很实用——比如被问"Python 的 sorted() 稳定吗？"时，可以顺着 Timsort/Powersort 的稳定性与 O(n log n) 复杂度展开。

边界情况（Corner Cases）

原文档列出的边界情况清单同样是二分与排序实现的自测清单，任何手写二分/排序代码都应逐条过一遍：

• 空序列（Empty sequence）
• 只有一个元素的序列
• 有两个元素的序列
• 含重复元素的序列

仓库中自带的参考实现正是按这套清单写的测试用例，例如 mergeSort.js 就依次验证了空数组、单元素、双元素、含重复元素（[7, 2, 4, 3, 1, 2] 期望 [1, 2, 2, 3, 4, 7]）、已有序数组与含负数的数组，可作为自测模板直接沿用。

二分搜索的无溢出迭代实现

速查文档的核心结论——"有序输入首先想到二分"——在仓库中有可直接运行的参考实现。JavaScript 版本见 binarySearch.js：

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;
  while (left <= right) {
    const mid = left + Math.floor((right - left) / 2);
    if (arr[mid] === target) {
      return mid;
    }
    if (arr[mid] < target) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return -1;
}

Python 等价实现见 binary_search.py：

def binary_search(arr, target):
    left = 0
    right = len(arr) - 1
    while left <= right:
        mid = left + (right - left) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

两处实现都体现了两个关键工程细节，面试手撕时应当刻意保留：

1. 中点计算用 left + (right - left) // 2 而非 (left + right) // 2。在 C/Java 等语言中 left + right 可能溢出，这种写法避免了该问题；
2. 循环条件 left <= right 且返回 -1 表示未命中，而不是返回布尔值——返回下标能让调用方拿到目标位置。

两个文件末尾都附带了断言式自测：对 [1, 2, 3, 10] 分别查找首元素、中间元素、尾元素、不存在元素、小于首元素与大于尾元素的值，全部符合预期，覆盖了"命中/不命中/越界两侧"的组合。

bisect 变体：处理重复元素与"插入位置"

binary_search.py 还实现了二分搜索最重要的两个变体 bisect_left 和 bisect_right，它们回答的问题不是"目标在哪"，而是"目标应该插到哪里才能保持有序"：

def bisect_left(arr, target):
    """Returns the leftmost position that `target` should
    go to such that the sequence remains sorted."""
    left = 0
    right = len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] < target:
            left = mid + 1
        else:
            right = mid
    return left

def bisect_right(arr, target):
    """Returns the rightmost position that `target` should
    go to such that the sequence remains sorted."""
    left = 0
    right = len(arr)
    while left < right:
        mid = (left + right) // 2
        if arr[mid] > target:
            right = mid
        else:
            left = mid + 1
    return left

注意与基础二分的三点结构差异：搜索区间右端是 len(arr) 而非 len(arr) - 1（允许插入到末尾）；循环条件是 left < right（左闭右开区间）；比较方向不同（bisect_left 用 <，bisect_right 用 >）。文件内的自测用例（第 50-68 行）特别验证了重复元素场景：对 [1, 2, 3, 3, 10] 查找 3，bisect_left 返回 2（第一个 3 的位置），bisect_right 返回 4（最后一个 3 之后的位置）——这正是原文档"含重复元素的序列"这一边界情况的具体化。这类变体是 "Search in Rotated Sorted Array"、统计区间内元素个数等高频题的骨架。

归并排序实现：为什么它的空间是 O(n)

仓库中 mergeSort.js 提供了一个标准的递归归并排序实现，恰好印证了复杂度表中的空间一栏：

function mergeSort(arr) {
  if (arr.length < 2) {
    // Arrays of length 0 or 1 are sorted by definition.
    return arr;
  }

  const left = arr.slice(0, Math.floor(arr.length / 2));
  const right = arr.slice(Math.floor(arr.length / 2), arr.length);

  return merge(mergeSort(left), mergeSort(right));
}

function merge(arr1, arr2) {
  const merged = [];
  let i = 0, j = 0;

  while (i < arr1.length && j < arr2.length) {
    if (arr1[i] <= arr2[j]) {
      merged.push(arr1[i]);
      i++;
    } else if (arr2[j] < arr1[i]) {
      merged.push(arr2[j]);
      j++;
    }
  }

  merged.push(...arr1.slice(i), ...arr2.slice(j));
  return merged;
}

从源码结构看，每个 slice 与 merged 数组都会分配新内存，递归深度为 log n、每层合计复制 n 个元素，因此总空间开销是 O(n)——这就是它与原地排序（O(1) 空间的 Heapsort）的核心取舍，也是 Mergesort 稳定（<= 比较保证相等元素保持原相对顺序）而 Heapsort 不稳定（见 heap.py 中 _bubble_down 选较小子节点时左子优先的写法）的原因。虽然面试不要求你默写归并排序，但理解"为什么需要额外 O(n) 空间"能在复杂度讨论中体现深度。文件末尾（第 34-50 行）的自测用例覆盖了原文档列出的全部边界情况：空数组、单元素、双元素、重复元素、逆序数组以及含负数数组。

从排序到选择：QuickSelect 与 K 大问题

原文档推荐练习题中包含 "Kth Largest Element in an Array" 这类 K 大问题。这类问题的最优解法不是完整排序，而是 QuickSelect——基于快排 partition 思想的线性时间选择算法。仓库中的 quick_select.py 给出了可运行实现：

def quick_select(array, k):
    """NOTE: k-th smallest element counts from 0!"""
    left = 0
    right = len(array)
    while True:
        random_index = random.sample(range(left, right), 1)[0]
        array[left], array[random_index] = array[random_index], array[left]
        pivot_index = partition_first(array, left, right)
        if k == pivot_index:
            return array[pivot_index]
        if k < pivot_index:
            right = pivot_index
        else:
            left = pivot_index + 1

实现要点从源码中可以读出：随机化选轴元（避免最坏 O(n²)）；partition_first 变体保证轴元落在其最终排序位置（这是正确性前提）；每轮只递归/循环进入一侧，因此期望复杂度 O(n)。文件末尾（第 50-60 行）用 1000 个元素随机打乱 10 次的随机化测试来验证，这种"大规模随机自测"的写法在面试白板之外非常实用。

面试中的两类识别技巧

原文档的 Techniques 一节给出了两条题目识别规则，这是把"排序/搜索"专题落地到具体题目的桥梁：

1. 输入已经有序（Sorted inputs）

当给定序列本身有序（无论升序还是降序）时，二分搜索应该是你脑海中第一个跳出来的工具。

这一条覆盖的题型包括：有序数组/旋转有序数组中的搜索、二维有序矩阵的搜索、用二分"搜索答案"的单调性问题（如求最小的 x 使 f(x) 成立）。前面讲的 bisect 变体正是这条技巧的具体工具。

2. 值域有限的输入（Limited range）

计数排序（Counting sort）是一种非比较排序，适用于事先已知取值范围的数值。原文档给出的例子是 H-Index 问题。

当 n 很大但值域 k 很小（或 k 与 n 同量级）时，O(n + k) 的计数排序可以击败 O(n log n) 的比较排序，这也解释了复杂度表中为什么单独列出 Counting sort 与 Radix sort。

刷题清单：必备题与推荐题

原文档将练习分为"必备题"（学习本专题时优先刷）与"推荐题"（学完必备题后刷），以下为完整继承的清单：

必备题（Essential questions）：

• Binary Search（LeetCode 704）——二分基础模板题
• Search in Rotated Sorted Array（LeetCode 33）——有序性被破坏后的二分

推荐练习题（Recommended practice questions）：

• Kth Smallest Element in a Sorted Matrix（LeetCode 378）——有序结构上的二分
• Search a 2D Matrix（LeetCode 74）——把二维矩阵"摊平"成一维二分
• Kth Largest Element in an Array（LeetCode 215）——QuickSelect 的直接应用
• Find Minimum in Rotated Sorted Array（LeetCode 153）——旋转数组中用二分找拐点
• Median of Two Sorted Arrays（LeetCode 4）——两个有序数组上的二分，难度上限

这份清单与仓库内参考实现的对应关系很直接：旋转数组两题练"有序性判定"，Kth 两题练"二分/选择代替全排序"，矩阵两题练"降维后二分"，Median 一题练"对答案空间二分"。

学习资源（按原文档继承）

原文档按"阅读/加餐/视频"三层组织了学习资源。外部链接因平台规范不再列出，但保留其来源与主题供检索：

• 核心阅读：basecs 的排序算法基础文、Khan Academy 的 Binary Search 讲解；
• 加餐（有时间再看）：basecs 系列文章，覆盖 Selection Sort、Bubble Sort、Insertion Sort、Merge Sort（上下篇）、Quicksort（上下篇）、Counting Sort、Radix Sort；
• 视频系列：剑桥大学 Samuel Albanie 的算法短视频，覆盖 Heapsort、Quicksort、比较排序下界（Lower bounds for comparison sorts）、Counting sort、Radix sort、Bucket sort，每支视频均配有 slides。

仓库本身也提供了算法课程的推荐入口（见 AlgorithmCourses.md），按专题文档的引用方式挂载在本页末尾。

小结

排序与搜索专题在面试中的真实分工是：排序靠语言内置函数（Python 3.11+ 的 Powersort、Java 的 Timsort/双轴快排），搜索才是手撕重点。建议的掌握路径是：先背下复杂度对照表 → 用 binarySearch.js 与 binary_search.py 把基础二分和 bisect 变体各手撕两遍并跑通自带自测用例 → 理解 mergeSort.js 的 O(n) 空间来源 → 通过 quick_select.py 建立"选择代替排序"的直觉 → 按必备题、推荐题顺序完成刷题，并对每个实现逐条核对原文档的四类边界情况（空、单元素、双元素、重复元素）。