搜索与排序算法全景
12400
画布
|大纲
内容详情
搜索算法
分类与核心思想
- 顺序搜索
- 适用场景
- 无序或有序数据均可
- 核心思想
- 逐个遍历比较
- 代表算法
- 线性搜索（Linear Search）
- 适用场景
- 区间搜索
- 适用场景
- 仅已排序数据
- 核心思想
- 分治减半
- 代表算法
- 二分搜索（Binary Search）
- 适用场景
线性搜索
- 执行步骤
- 遍历
- 循环覆盖全部元素
- 比较
- 元素==目标值即返回索引
- 未命中
- 遍历结束返回-1
- 遍历
- 代码实现
- Java示例
- 循环+
- Java示例
- 时间复杂度
- 最坏
- O(n) 需遍历全部
- 最好
- Ω(1) 首元素即命中
- 最坏
二分搜索
- 前提条件
- 数据已排序
- 升/降序均可，需与比较逻辑一致
- 数据已排序
- 执行步骤
- 初始化
- start=0, end=n-1
- 迭代
- mid=(start+end)/2
- 目标<mid → end=mid-1
- 目标>mid → start=mid+1
- 终止
- 命中返回mid；start>end返回-1
- 初始化
- 代码实现
- Java示例
- +mid更新
- Java示例
- 时间复杂度
- 最坏
- O(log n) 每次减半
- 最好
- Ω(1) 首次mid即命中
- 最坏
算法对比
- 数据要求
- 线性搜索
- 无需排序
- 二分搜索
- 必须排序
- 线性搜索
- 遍历方式
- 线性搜索
- 逐个扫描
- 二分搜索
- 跳跃式减半
- 线性搜索
- 最坏复杂度
- 线性搜索
- O(n)
- 二分搜索
- O(log n)
- 线性搜索
- 适用场景
- 线性搜索
- 小规模、无序
- 二分搜索
- 大规模、有序
- 线性搜索
排序算法
基础排序
- 冒泡排序
- 思想
- 相邻比较交换，大元素“上浮”
- 复杂度
- 平均/最坏O(n²)
- 思想
- 选择排序
- 思想
- 每轮选最小值放已排序区末尾
- 复杂度
- 平均/最坏O(n²)
- 思想
- 插入排序
- 思想
- 逐个插入已排序区合适位置
- 复杂度
- 平均/最坏O(n²)
- 思想
进阶排序
- 快速排序
- 思想
- 选基准分治，递归排序左右子数组
- 复杂度
- 平均O(n log n)，最坏O(n²)
- 思想
- 归并排序
- 思想
- 分两半分别排序再合并
- 复杂度
- 稳定O(n log n)
- 思想
- 堆排序
- 思想
- 构建大顶堆，反复取堆顶并调整
- 复杂度
- O(n log n)，原地不稳定
- 思想