Cao Note

外观

排序与查找 ​

八大排序的思路、复杂度、稳定性、是否原地，外加二分查找的全部变体与 TopK、海量数据外排序。排序是"让暴力变优雅"的第一步。

一、排序基础概念 ​

1.1 稳定性与原地排序 ​

  • 稳定：相等元素的相对顺序排序后不变（对"先按 A 排、再按 B 排"的多关键字排序重要）。
  • 原地（in-place）：额外空间 O(1)；非原地如归并需要 O(n) 辅助数组。
  • 两者独立：选择排序原地但不稳定；归并排序稳定但非原地。

1.2 基于比较 vs 非比较 ​

  • 基于比较的排序（插入/冒泡/选择/归并/快排/堆排）理论下界 O(n log n)。
  • 非比较排序（计数/桶/基数）利用数据分布特性，可做到 O(n)，但有前提。

二、O(n²) 排序一：插入排序 ​

2.1 思路 ​

  • 像抓扑克牌：把当前元素插入到左侧已排好序列的正确位置。
[5| 3 8 1] → 把 3 插入有序段 [5] → [3 5 | 8 1] → [3 5 8 | 1] → [1 3 5 8]
  已排区↑
[5| 3 8 1] → 把 3 插入有序段 [5] → [3 5 | 8 1] → [3 5 8 | 1] → [1 3 5 8]
  已排区↑
python
def insertion_sort(a):
    for i in range(1, len(a)):
        cur = a[i]
        j = i - 1
        while j >= 0 and a[j] > cur:   # 已排区从右往左找位置
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = cur
    return a
def insertion_sort(a):
    for i in range(1, len(a)):
        cur = a[i]
        j = i - 1
        while j >= 0 and a[j] > cur:   # 已排区从右往左找位置
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = cur
    return a

2.2 复杂度与性质 ​

项值
平均/最坏O(n²)（逆序时每次都要搬移）
最好O(n)（已有序，内层不搬移）
稳定性稳定
原地是
空间O(1)

2.3 适用场景 ​

  • 数据量小、或近乎有序的数据（如"纠错一个乱序元素"）时接近 O(n)，比快排还快。

三、冒泡排序 ​

3.1 思路 ​

  • 相邻两两比较，逆序就交换，每轮把当前最大"冒"到末尾。
第一轮： [5 3 8 1] → [3 5 1 |8]   （8 冒到最右）
第二轮： [3 1 |5 8]
第三轮： [1 |3 5 8]
第一轮： [5 3 8 1] → [3 5 1 |8]   （8 冒到最右）
第二轮： [3 1 |5 8]
第三轮： [1 |3 5 8]
python
def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:      # 优化：本轮无交换即已有序
            break
    return a
def bubble_sort(a):
    n = len(a)
    for i in range(n - 1):
        swapped = False
        for j in range(n - 1 - i):
            if a[j] > a[j + 1]:
                a[j], a[j + 1] = a[j + 1], a[j]
                swapped = True
        if not swapped:      # 优化：本轮无交换即已有序
            break
    return a

3.2 提前终止优化 ​

  • 记录每轮是否发生过交换：没交换说明全部有序，提前退出 → 最好情况 O(n)。
  • 复杂度：平均/最坏 O(n²)，稳定，原地。

四、选择排序 ​

4.1 思路 ​

  • 每轮从未排区选出最小值，与未排区第一个位置交换。
[5 3 8 1] → 选最小 1 → [1 | 3 8 5] → 选最小 3 → [1 3 | 8 5] → [1 3 5 | 8]
[5 3 8 1] → 选最小 1 → [1 | 3 8 5] → 选最小 3 → [1 3 | 8 5] → [1 3 5 | 8]

4.2 为什么不稳定 ​

  • 例：[2a, 2b, 1]，第一轮把 1 与 2a 交换 → [1, 2b, 2a]，两个 2 的相对顺序变了。
  • 复杂度：任何情况都 O(n²)（无论如何都要扫描完找最小），原地，不稳定。
  • 意义：交换次数最少（≤ n-1 次），对"写操作代价高"的场景有价值。

五、归并排序（分治） ​

5.1 思路 ​

  • 分：数组对半切到单元素；治：两个有序段双指针合并。
[5 3 8 1]
  /    \
[5 3] [8 1]     → 切分
 / \   / \
[5][3][8][1]     → 合并：[3 5] 与 [1 8]
  \   /  \   /   → [1 3 5 8]
[5 3 8 1]
  /    \
[5 3] [8 1]     → 切分
 / \   / \
[5][3][8][1]     → 合并：[3 5] 与 [1 8]
  \   /  \   /   → [1 3 5 8]
python
def merge_sort(a):
    if len(a) <= 1: return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    i = j = 0; res = []
    while i < len(left) and j < len(right):    # 合并两个有序段
        if left[i] <= right[j]:
            res.append(left[i]); i += 1
        else:
            res.append(right[j]); j += 1
    return res + left[i:] + right[j:]
def merge_sort(a):
    if len(a) <= 1: return a
    mid = len(a) // 2
    left, right = merge_sort(a[:mid]), merge_sort(a[mid:])
    i = j = 0; res = []
    while i < len(left) and j < len(right):    # 合并两个有序段
        if left[i] <= right[j]:
            res.append(left[i]); i += 1
        else:
            res.append(right[j]); j += 1
    return res + left[i:] + right[j:]

5.2 复杂度与性质 ​

项值
时间O(n log n) 稳定不变（好坏都如此）
空间O(n)（合并辅助数组）+ O(log n) 递归栈
稳定性稳定
原地否

5.3 应用：求逆序对 ​

  • 合并时若 left[i] > right[j]，则 left 中 i 之后全部大于 right[j]，一次累加 len(left) - i 个逆序对。
  • 复杂度仍是 O(n log n)；暴力双层循环是 O(n²) 必超时。

六、快速排序 ​

6.1 思路（分区 partition） ​

  • 选一个基准 pivot，把数组分成"小于 pivot / pivot / 大于 pivot"三区，再递归两边。
pivot=5: [3 1 |5| 8 9] → 左区排好 + 5 + 右区排好 → 整体有序
pivot=5: [3 1 |5| 8 9] → 左区排好 + 5 + 右区排好 → 整体有序
python
def quick_sort(a):
    if len(a) <= 1: return a
    pivot = a[len(a) // 2]
    lo  = [x for x in a if x < pivot]
    eq  = [x for x in a if x == pivot]
    hi  = [x for x in a if x > pivot]
    return quick_sort(lo) + eq + quick_sort(hi)
def quick_sort(a):
    if len(a) <= 1: return a
    pivot = a[len(a) // 2]
    lo  = [x for x in a if x < pivot]
    eq  = [x for x in a if x == pivot]
    hi  = [x for x in a if x > pivot]
    return quick_sort(lo) + eq + quick_sort(hi)

6.2 复杂度与退化 ​

项值
平均O(n log n)
最坏O(n²)（每次 pivot 都是极值：有序数组 + 固定取首/尾）
空间O(log n)~O(n)（递归栈）
稳定性不稳定（交换会打乱相等元素）
原地标准写法原地（上例为教学版非原地）

6.3 优化手段 ​

  • 随机化基准：随机选 pivot，使退化概率极低。
  • 三数取中：取首/中/尾的中位数做 pivot。
  • 三路快排：分成 < / = / > 三区，大量重复元素时从 O(n²) 变 O(n)。
  • 小数组转插入排序：长度 < 阈值（如 16）时插入排序更快。
  • 工程上 Java Arrays.sort 对基本类型用双轴快排、对象用归并（稳定）。

七、堆排序 ​

7.1 思路 ​

  • 先建堆（大顶堆），再反复把堆顶（最大）与末尾交换、缩小堆范围并下沉。
建堆后： [9 6 8 3 1]
pop 堆顶 9 与末尾交换 → [1 6 8 3 |9] → 下沉 → [8 6 1 3 |9] → ...
建堆后： [9 6 8 3 1]
pop 堆顶 9 与末尾交换 → [1 6 8 3 |9] → 下沉 → [8 6 1 3 |9] → ...

7.2 性质 ​

项值
时间O(n log n)（任何情况）
空间O(1)（原地）
稳定性不稳定（堆顶交换跳过中间相等元素）
适用数据量极大且要求原地 O(n log n)、或"只要前 K 个"时用堆更划算

八、线性排序（非比较） ​

8.1 计数排序 ​

  • 前提：数据是范围有限的小整数（如成绩 0~100）。开计数数组统计频次，再按频次回填。
python
def counting_sort(a, max_val):
    cnt = [0] * (max_val + 1)
    for x in a: cnt[x] += 1
    res = []
    for v, c in enumerate(cnt):
        res.extend([v] * c)
    return res
def counting_sort(a, max_val):
    cnt = [0] * (max_val + 1)
    for x in a: cnt[x] += 1
    res = []
    for v, c in enumerate(cnt):
        res.extend([v] * c)
    return res
  • 时间 O(n+k)、空间 O(k)（k 为值域）；稳定版本用前缀和 + 倒序回填。

8.2 桶排序 ​

  • 把数据按范围分到若干"桶"，桶内各自排序（常用插入/快排），再按桶序合并。
  • 时间：数据均匀时 O(n)；空间 O(n+m)。适合浮点、分布均匀的数据。

8.3 适用前提对比 ​

排序前提时间空间
计数非负小整数，k 可控O(n+k)O(k)
桶分布均匀可分桶O(n) 平均O(n+m)
基数定长数字/字符串O(d·(n+k))O(n+k)

九、排序算法对比总表 ​

9.1 全部指标总表 ​

排序平均最坏最好空间稳定原地思路一句话
插入O(n²)O(n²)O(n)O(1)稳定是摸牌插到有序区
冒泡O(n²)O(n²)O(n)O(1)稳定是相邻交换冒泡
选择O(n²)O(n²)O(n²)O(1)不稳是每轮选最小交换
归并O(n log n)O(n log n)O(n log n)O(n)稳定否分治合并有序段
快排O(n log n)O(n²)O(n log n)O(log n)不稳是分区递归
堆排O(n log n)O(n log n)O(n log n)O(1)不稳是建堆反复取顶
计数O(n+k)O(n+k)O(n+k)O(k)稳定*否频次回填
桶O(n)O(n²)O(n+k)O(n+m)稳定*否分桶各排

*计数/桶在正确实现下可稳定；*空间不把输入数组本身计入。

9.2 工程内建排序选型 ​

  • Java：基本类型 Arrays.sort → 双轴快排（不稳定）；对象 → TimSort/归并（稳定）。
  • Python：list.sort() / sorted 是 Timsort（归并+插入混合），稳定、O(n log n)。
  • 面试被问「写一个稳定的原地排序」：理论上是伪命题（稳定与原地难以兼得），应指出可用插入排序（O(n²)）。

十、TopK 问题 ​

10.1 三种主流做法 ​

方法思路时间空间适用
全排序排完取前 KO(n log n)O(1)K 接近 n、追求简单
堆维护大小 K 的小顶堆（求前 K 大）O(n log K)O(K)海量数据、流式数据
快速选择快排 partition 只递归一边O(n) 平均O(log n)K 明显小于 n 且数组在内存

10.2 堆做法与快速选择 ​

python
import heapq
def top_k_largest(a, k):      # 前 K 大：维护大小为 K 的小顶堆
    return heapq.nlargest(k, a)
# 原理：堆顶是当前 K 个里最小的，新元素比它大就替换 → 堆里永远是最大的 K 个
import heapq
def top_k_largest(a, k):      # 前 K 大：维护大小为 K 的小顶堆
    return heapq.nlargest(k, a)
# 原理：堆顶是当前 K 个里最小的，新元素比它大就替换 → 堆里永远是最大的 K 个
  • 快速选择：partition 后看 pivot 下标，等于 k-1 即答案；只递归含 k 的一侧 → 平均 O(n)。
  • 题感：求第 K 大/小用快速选择或堆；求前 K 个且数据流式只能用堆。

十一、二分查找 ​

11.1 基础模板与易错点 ​

  • 前提：单调有序序列。每轮砍一半 → O(log n)。
python
def binary_search(a, target):
    lo, hi = 0, len(a)          # 左闭右开 [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo if lo < len(a) and a[lo] == target else -1
def binary_search(a, target):
    lo, hi = 0, len(a)          # 左闭右开 [lo, hi)
    while lo < hi:
        mid = (lo + hi) // 2
        if a[mid] < target:
            lo = mid + 1
        else:
            hi = mid
    return lo if lo < len(a) and a[lo] == target else -1
  • 易错点：lo <= hi 与 lo < hi 两套写法别混；死循环常因 lo = mid（未 +1）；mid 用 (lo+hi)//2 防溢出（Python 无所谓，Java/C++ 大数会溢出）。

11.2 查找左边界与右边界 ​

  • 第一个 ≥ target（lower_bound）：上面模板的返回值即左边界。
  • 第一个 > target（upper_bound）：a[mid] <= target 时 lo = mid+1。
  • 组合出：等于 target 的区间 = [lower_bound, upper_bound)。

11.3 旋转数组（部分有序仍可二分） ​

  • 特征：升序数组在某点旋转，如 [4,5,6,7,0,1,2]。二分时判断 mid 落在左半有序还是右半有序，再决定搜索方向。
python
def search_rotated(a, target):     # 无重复元素版
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target: return mid
        if a[lo] <= a[mid]:              # 左半有序
            if a[lo] <= target < a[mid]: hi = mid - 1
            else: lo = mid + 1
        else:                            # 右半有序
            if a[mid] < target <= a[hi]: lo = mid + 1
            else: hi = mid - 1
    return -1
def search_rotated(a, target):     # 无重复元素版
    lo, hi = 0, len(a) - 1
    while lo <= hi:
        mid = (lo + hi) // 2
        if a[mid] == target: return mid
        if a[lo] <= a[mid]:              # 左半有序
            if a[lo] <= target < a[mid]: hi = mid - 1
            else: lo = mid + 1
        else:                            # 右半有序
            if a[mid] < target <= a[hi]: lo = mid + 1
            else: hi = mid - 1
    return -1
  • 有重复元素时退化为 O(n)（a[lo]==a[mid]==a[hi] 时只能缩一位）。
  • 变体题：找旋转点（最小值）下标、寻找峰值。

11.4 答案二分（对"值"二分） ​

  • 识别信号：求"最大化的最小值 / 最小化的最大值"（如分巧克力、运包裹能力、磁力球）。
  • 套路：对答案值域二分，用贪心 check(mid) 判断可行性，把最优化问题转判定问题。

十二、海量数据外排序 ​

12.1 内存装不下怎么办 ​

  • 数据量远超内存（如 100GB 文件）无法整体读入排序。
  • 通用框架 = 外部归并排序：分块读入 → 块内排好写回 → 多路归并。

12.2 多路归并思路 ​

阶段一（分割）：100GB 分成 100 个 1GB 块，每块内存排序后写回磁盘。
阶段二（归并）：K 路归并——用大小为 K 的小顶堆，每次取 K 个文件块中
              最小的元素写出，堆顶所在文件块补下一个元素。
阶段一（分割）：100GB 分成 100 个 1GB 块，每块内存排序后写回磁盘。
阶段二（归并）：K 路归并——用大小为 K 的小顶堆，每次取 K 个文件块中
              最小的元素写出，堆顶所在文件块补下一个元素。
  • 归并路数 K 越大，磁盘 IO 轮数越少（log_K 轮），但每轮堆开销增大。

12.3 复杂度与工程要点 ​

项值
时间O(n log n)（与内存排序同量级）+ IO 代价
IO关键瓶颈：读 1 遍 + 写 1 遍 × log_K(n/M) 轮
注意增大缓冲区减少磁盘寻道；也可用快排先做块内排序再归并
  • 面试话术：先答"分治 + K 路归并"，再答堆选最小、缓冲区与 IO 轮数，体现对磁盘瓶颈的意识。

Copyright © 2024-present xiaocao