Algorithms study cheatsheets

Coding interview 的 Sorting & Searching cheatsheet

Sorting/Searching 学习指南，包含练习题、技巧、时间复杂度与推荐资源

Introduction

Sorting 是把序列按数值或字典序排序，且可升序或降序。

很多基础排序算法是 O(n²)，面试中不建议手写。实际面试里，你通常用语言自带的排序函数，然后基于排序结果做 binary search。

在 sorted array 上，利用有序性可以用 binary search，把查找从 O(n) 降到 O(log n)。binary search 通过比较中间元素来决定向左还是向右，直到找到目标或区间为空。

Learning resources

虽然面试不要求你手写排序，但了解不同排序算法的复杂度很有用。

Readings
- Sorting Out The Basics Behind Sorting Algorithms, basecs
- Binary Search, Khan Academy
Additional (only if you have time)
- Exponentially Easy Selection Sort, basecs
- Bubbling Up With Bubble Sorts, basecs
- Inching Towards Insertion Sort, basecs
- Making Sense of Merge Sort (Part 1), basecs
- Making Sense of Merge Sort (Part 2), basecs
- Pivoting To Understand Quicksort (Part 1), basecs
- Pivoting To Understand Quicksort (Part 2), basecs
- Counting Linearly With Counting Sort, basecs
- Getting To The Root Of Sorting With Radix Sort, basecs
Videos
- Heapsort (slides), Samuel Albanie, University of Cambridge
- Quicksort (slides), Samuel Albanie, University of Cambridge
- Lower bounds for comparison sorts (slides), Samuel Albanie, University of Cambridge
- Counting sort (slides), Samuel Albanie, University of Cambridge
- Radix sort (slides), Samuel Albanie, University of Cambridge
- Bucket sort (slides), Samuel Albanie, University of Cambridge

Time complexity

Algorithm	Time	Space
Bubble sort	O(n²)	O(1)
Insertion sort	O(n²)	O(1)
Selection sort	O(n²)	O(1)
Quicksort	O(nlog(n))	O(log(n))
Mergesort	O(nlog(n))	O(n)
Heapsort	O(nlog(n))	O(1)
Counting sort	O(n + k)	O(k)
Radix sort	O(nk)	O(n + k)

Algorithm	Big-O
Binary search	O(log(n))

面试时需要注意

务必知道语言默认排序算法的 time/space complexity（基本是 O(n log n)）。如果能说出算法名称会加分。Python 3.11+ 默认是 Powersort，替代了 Timsort。Java 对对象排序用 Timsort 实现，对原始类型用 Dual-Pivot Quicksort。

Corner cases

Empty sequence
只有 1 个元素
只有 2 个元素
有重复元素

Techniques

Sorted inputs

若序列已排序（升序或降序），binary search 应该是第一反应。

Sorting with limited range

Counting sort 是非比较排序，适用于数值范围已知的情况。Examples: H-Index

Essential questions

该 topic 必练题。