全部类别

查找与排序12

查找位置、选择元素、排序与归并,分析输入条件和复杂度。

排序

把元素按键或比较规则排成有序序列。选择时需要区分稳定性、额外空间、键的表示和输入是否已有序。

适用条件与算法对照
顺序查找Linear search

依次检查候选,直到找到目标或遍历结束。

最坏 O(n)O(n),额外空间 O(1)O(1)

小集合、无序输入、顺序数据流。

快速选择Quickselect

分区后只处理包含第 k 小元素的一侧。

常见随机化实现期望 O(n)O(n),最坏 O(n2)O(n^{2})

分位数、中位数与无需全排序的 Top-K 边界。

12 个概念