比较排序:
- 插入排序: O(n²) 最坏/平均，O(n) 最好（已排序）
- 选择排序: O(n²) 所有情况
- 归并排序: O(n log n) 所有情况
- 快速排序: O(n log n) 平均，O(n²) 最坏
- 堆排序: O(n log n) 所有情况

线性排序（非比较）:
- 计数排序: O(n + k)，k 为值域
- 基数排序: O(d(n + k))，d 为位数
- 桶排序: O(n + k) 平均

快速排序的平均复杂度:

设 C(n) 为 n 个元素的平均比较次数
C(n) = n - 1 + (1/n) Σ_{k=0}^{n-1} [C(k) + C(n-1-k)]

解: C(n) = 2(n+1)Hₙ - 4n ≈ 1.386 n log₂ n

其中 Hₙ = 1 + 1/2 + 1/3 + ... + 1/n ≈ ln n + 0.5772

最坏情况: 每次划分极度不平衡
C_worst(n) = n(n-1)/2 = O(n²)
（当数组已排序且选择第一个元素为 pivot 时）

避免最坏情况:
1. 随机选择 pivot
2. 三数取中（首、尾、中间的中位数）
3. IntroSort（快速排序 + 堆排序 + 插入排序）

散列函数:
h(key) → 桶地址

好的散列函数:
- 均匀分布
- 雪崩效应（输入微小变化导致输出大幅变化）
- 计算快速

冲突解决:
1. 链地址法: 每个桶维护一个链表
   - 查找: O(1 + α)，α = n/m (负载因子)
   
2. 开放寻址法:
   - 线性探测: h(k), h(k)+1, h(k)+2, ...
     → 一次聚集问题
   - 二次探测: h(k), h(k)+1, h(k)+4, h(k)+9, ...
   - 双重散列: h₁(k), h₁(k)+h₂(k), h₁(k)+2h₂(k), ...

负载因子 α = n/m:
- α < 0.7: 性能良好
- α → 1: 性能急剧下降
- 解决方案: 动态扩容（α 超过阈值时翻倍）

顺序查找:
- 无序表: O(n)
- 有序表: O(n)

二分查找:
- 有序表: O(log n)
- 精确比较次数: ⌊log₂ n⌋ + 1

散列查找:
- 平均: O(1)
- 最坏: O(n)（所有元素冲突）

查找算法选择:
- 数据量小 (< 100): 顺序查找
- 静态有序数据: 二分查找
- 动态数据: 散列或平衡树
- 需要范围查询: 平衡树（B+ 树）

import random

def quicksort(arr):
    if len(arr) <= 1:
        return arr, 0
    pivot = arr[0]
    left = [x for x in arr[1:] if x <= pivot]
    right = [x for x in arr[1:] if x > pivot]
    left_sorted, left_cmp = quicksort(left)
    right_sorted, right_cmp = quicksort(right)
    comparisons = len(arr) - 1 + left_cmp + right_cmp
    return left_sorted + [pivot] + right_sorted, comparisons

# 统计平均比较次数
import statistics
results = []
for _ in range(1000):
    arr = list(range(100))
    random.shuffle(arr)
    _, cmps = quicksort(arr)
    results.append(cmps)

avg = statistics.mean(results)
print(f"n=100, 平均比较次数: {avg:.1f}")
print(f"理论值: 2 × 101 × H₁₀₀ - 4 × 100 = {2 * 101 * sum(1/i for i in range(1, 101)) - 400:.1f}")

# 典型输出:
# n=100, 平均比较次数: 648.3
# 理论值: 648.5