学习数据结构时的查找与排序总结

查找算法

这学期数据结构课学了不少查找和排序算法，趁还记得清楚的时候整理一下笔记。

顺序查找

最简单的查找方式，从头到尾遍历。时间复杂度 O(n)，适合无序小数据集。代码很简单：

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

二分查找

要求数据有序，每次比较后将搜索范围缩小一半。时间复杂度 O(log n)，是考试重点：

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

哈希查找

平均时间复杂度 O(1)，但需要处理冲突。常见冲突处理方法：

• 拉链法 — 同一个桶用链表存储多个元素
• 开放寻址法 — 冲突时找下一个空桶

哈希查找适合精确匹配，不适合范围查询。

排序算法

O(n²) 排序

冒泡排序和选择排序好理解但效率低，实际项目中基本不会用。插入排序在数据基本有序时效率还不错。

O(n log n) 排序

| 算法 | 最好 | 最坏 | 空间 | 稳定性 | |------|------|------|------|--------| | 快排 | O(n log n) | O(n²) | O(log n) | 不稳定 | | 归并 | O(n log n) | O(n log n) | O(n) | 稳定 | | 堆排 | O(n log n) | O(n log n) | O(1) | 不稳定 |

快排是实际最常用的，虽然最坏情况 O(n²) 但平均 O(n log n)，常数因子小。

归并排序稳定但需要额外空间，适合对稳定性有要求的场景。

堆排序时间复杂度稳定但缓存局部性差，实际运行效率不如快排。

适用场景总结

理解算法的关键不是背代码，而是理解每种算法的适用场景和权衡：

• 数据量小 → 插入排序
• 通用排序 → 快排
• 需要稳定性 → 归并排序
• 空间受限 → 堆排序
• 数据基本有序 → 插入排序

这些在做题和实际编程中都会用到。