您的位置: 首页 > 文章 > 【算法导论学习笔记】---选择算法

【算法导论学习笔记】---选择算法

分类: 文章 • 2025-03-09 20:48:28

找到数组中某个特定大小顺序的数，比如第i小的数
- 随机选择算法：RANDOMIZED-SELECT
  - 期望运行时间为：O[n]
  - 思想：借助快速排序的想法，将数组划分为两部分（比x大和比x小），不同的是我们只需要去关注一部分。
- 快速选择算法：SELECT
  - 最坏运行时间：O[n]
  - 思想：中位数的中位数，将数组分为5组（实际上只要组数大于等于5都是可以的，若小于5，运行时间就不是线性的了）
  - 应用：我们可以将快速选择算法应用到快速排序中去，具体来说，就是将快排中的partition使用SELECT代替，找到中间大的数，条件是每个元素互异。