快速选择算法,是一种能在大致O(N)的时间内选取数组中第k大或者k小的算法.其基本思路与快速排序算法类似,也是分治的思想.
其实这个算法是个基础算法,但是不常用,所以今天编的时候错了POJ2388,才有了这篇文章.
- 执行Partition算法(就是那个快排里将区间内所有数划分为小的一部分和大的一部分的过程)
- 判断第k大的数是在小的部分还是大的部分
- 递归,直到区间足够小,返回结果
快速选择算法,是一种能在大致O(N)的时间内选取数组中第k大或者k小的算法.其基本思路与快速排序算法类似,也是分治的思想.
其实这个算法是个基础算法,但是不常用,所以今天编的时候错了POJ2388,才有了这篇文章.