排序 & 搜索算法

排序让数据有序，搜索让查找高效。掌握它们的时间复杂度和适用场景，是写出高性能代码的基础。

---

一、排序算法速查

算法	平均	最好	最坏	空间	稳定	适用场景
冒泡排序	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²)	O(log n)	❌	大数据首选
归并排序	O(n log n)	O(n log n)	O(n log n)	O(n)	✅	需稳定排序、大文件
堆排序	O(n log n)	O(n log n)	O(n log n)	O(1)	❌	原地排序、Top K

稳定性

稳定：相同元素排序后，原来靠前的仍然靠前。冒泡、插入、归并稳定；选择、快速、堆不稳定。

---

二、排序算法实现

冒泡排序

每轮把最大值"冒泡"到末尾；加 swapped 优化后，已排序时 O(n) 提前退出。

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        swapped = False
        for j in range(n - i - 1):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
                swapped = True
        if not swapped:   # 本轮没有交换，已有序，提前结束
            break
    return arr

选择排序

每轮找最小元素放到已排序末尾，交换次数最少，但无论如何都要 O(n²) 次比较。

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

插入排序

将未排序元素插入到已排序部分的正确位置，类似整理扑克牌。数据基本有序时接近 O(n)。

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and key < arr[j]:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

快速排序

分治法。选基准（pivot），将数组分为小于/等于/大于三部分，递归排序。实际工程最常用。

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]           # 取中间元素为基准，减少最坏情况概率
    left   = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right  = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

最坏情况

当数组已有序且每次选首/尾为基准时，退化为 O(n²)。选取中间元素或随机基准可大幅降低概率。

归并排序

分治法。将数组二分后分别排序，再合并两个有序数组。时间复杂度稳定，是稳定排序中性能最好的。

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left  = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return _merge(left, right)

def _merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:     # <= 保证稳定性
            result.append(left[i]); i += 1
        else:
            result.append(right[j]); j += 1
    return result + left[i:] + right[j:]

堆排序

先建最大堆，再反复将堆顶（最大值）放到末尾并重新堆化，实现原地排序。

def heap_sort(arr):
    n = len(arr)

    def heapify(arr, n, i):
        largest = i
        left, right = 2*i+1, 2*i+2
        if left  < n and arr[left]  > arr[largest]: largest = left
        if right < n and arr[right] > arr[largest]: largest = right
        if largest != i:
            arr[i], arr[largest] = arr[largest], arr[i]
            heapify(arr, n, largest)

    # 1. Floyd 建堆 O(n)
    for i in range(n // 2 - 1, -1, -1):
        heapify(arr, n, i)
    # 2. 依次取出堆顶放到末尾
    for i in range(n - 1, 0, -1):
        arr[0], arr[i] = arr[i], arr[0]
        heapify(arr, i, 0)
    return arr

---

三、搜索算法速查

算法	时间复杂度	前提条件	适用场景
线性搜索	O(n)	无	无序小数据
二分查找	O(log n)	有序数组	有序数据快速查找
哈希表查找	O(1) 均摊	无	键值对快速查找
插值查找	O(log log n)	有序 + 均匀分布	均匀分布的有序数据
BFS	O(V+E)	图/树	最短路径（无权图）
DFS	O(V+E)	图/树	拓扑排序、连通性检测
布隆过滤器	O(k)	—	快速判断"一定不存在"

---

四、搜索算法实现

线性搜索

逐个遍历，无任何前提。

def linear_search(arr, target):
    for i, val in enumerate(arr):
        if val == target:
            return i
    return -1

二分查找

每次排除一半，必须有序数组。

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

arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 11]
print(binary_search(arr, 7))  # → 6

插值查找

根据数据分布预测位置，均匀分布时比二分更快。

mid = low + (target - arr[low]) × (high - low) / (arr[high] - arr[low])

def interpolation_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high and arr[low] <= target <= arr[high]:
        if arr[low] == arr[high]:   # 防止除零
            return low if arr[low] == target else -1
        mid = low + (target - arr[low]) * (high - low) // (arr[high] - arr[low])
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

插值 vs 二分

• 数据均匀分布时：插值查找 O(log log n) 比二分快
• 数据分布不均时：插值可能退化到 O(n)，不如二分稳定

BFS & DFS

以图遍历为例，两种策略的本质区别：

图结构：
A → B → D
      → E
  → C → F

from collections import deque

graph = {
    'A': ['B', 'C'], 'B': ['D', 'E'],
    'C': ['F'],      'D': [], 'E': [], 'F': []
}

# BFS：队列，逐层扩散，找最短路径
def bfs(graph, start):
    visited = set()
    queue = deque([start])
    order = []
    while queue:
        node = queue.popleft()
        if node not in visited:
            visited.add(node)
            order.append(node)
            queue.extend(n for n in graph[node] if n not in visited)
    return order

# DFS：递归/栈，一路深入，适合连通性检测
def dfs(graph, node, visited=None, order=None):
    if visited is None: visited = set()
    if order   is None: order   = []
    if node not in visited:
        visited.add(node)
        order.append(node)
        for neighbor in graph[node]:
            dfs(graph, neighbor, visited, order)
    return order

print(bfs(graph, 'A'))  # ['A', 'B', 'C', 'D', 'E', 'F']
print(dfs(graph, 'A'))  # ['A', 'B', 'D', 'E', 'C', 'F']

	BFS	DFS
数据结构	队列	栈（递归）
路径特点	找到的路径最短（无权图）	不保证最短
内存占用	较高（存整层节点）	较低（存路径深度）
典型应用	最短路径、社交好友推荐	拓扑排序、迷宫、连通性检测

布隆过滤器

用位数组 + 多个哈希函数判断元素是否存在：

• 返回"不存在" → 一定不存在（0 误判）
• 返回"存在" → 可能存在（有误判率，可调节）
• 不支持删除

import math, mmh3  # pip install mmh3

class BloomFilter:
    def __init__(self, capacity, error_rate=0.01):
        # 计算最优位数组大小和哈希函数数量
        self.size = math.ceil(-(capacity * math.log(error_rate)) / (math.log(2) ** 2))
        self.hash_count = math.ceil((self.size / capacity) * math.log(2))
        self.bits = [0] * self.size

    def _indices(self, item):
        return [abs(mmh3.hash(str(item), seed)) % self.size
                for seed in range(self.hash_count)]

    def add(self, item):
        for idx in self._indices(item):
            self.bits[idx] = 1

    def exists(self, item):
        return all(self.bits[idx] == 1 for idx in self._indices(item))

# 使用示例
bf = BloomFilter(capacity=1000, error_rate=0.01)
bf.add("apple")
bf.add("banana")

print(bf.exists("apple"))   # True（存在）
print(bf.exists("mango"))   # False（一定不存在）
print(bf.exists("cherry"))  # 大概率 False，极小概率 True（误判）

适用场景：缓存穿透防护、垃圾邮件过滤、爬虫 URL 去重。

---

五、跳表 Skip List

在有序链表基础上增加多级索引，实现近似 O(log n) 的查找，同时保留链表的 O(1) 插入删除优势。

Level 2:  1 ──────────────→ 9 ──→ None
Level 1:  1 ──────→ 6 ────→ 9 ──→ None
Level 0:  1 → 3 → 6 → 7 → 9 ──→ None

操作	平均复杂度	说明
查找	O(log n)	从高层索引开始跳跃
插入	O(log n)	随机决定层数
删除	O(log n)	更新各层指针

适用场景：Redis 有序集合（ZSet）的底层实现。