tech-interview-handbook 排序与搜索专题：复杂度对比、二分查找源码剖析与刷题路线
【免费下载链接】tech-interview-handbookCurated coding interview preparation materials for busy software engineers项目地址: https://gitcode.com/GitHub_Trending/te/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两处实现都体现了两个关键工程细节，面试手撕时应当刻意保留：
- 中点计算用
left + (right - left) // 2而非(left + right) // 2。在 C/Java 等语言中left + right可能溢出，这种写法避免了该问题； - 循环条件
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 建立"选择代替排序"的直觉 → 按必备题、推荐题顺序完成刷题，并对每个实现逐条核对原文档的四类边界情况（空、单元素、双元素、重复元素）。
【免费下载链接】tech-interview-handbookCurated coding interview preparation materials for busy software engineers项目地址: https://gitcode.com/GitHub_Trending/te/tech-interview-handbook
创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考
