【算法】归并排序
【算法】快速排序与归并排序对比
【算法】快速选择算法 ( 数组中找第 K 大元素 )
----
文章目录
算法 系列博客
一、快速选择算法
一、快速选择算法
----
数组中找第...K 大元素 : https://www.lintcode.com/problem/5/
可以 先进行 快速排序 , 然后找第 k 大的元素 ;
先排序 , 在获取值 , 会消耗 排序的时间复杂度...O(n \log n)
;
使用 快速选择算法 , 可以达到
O(n)
的时间复杂度 ;
快速选择算法 利用了快速排序算法的步骤 , 快速排序的第一个步骤是从数组中 挑选一个元素 p , 依据 p...O(n) + O(\cfrac{n}{2}) + T(\cfrac{n}{4})
时间复杂度计算时 , 只考虑最高次项 , 忽略常数 , 忽略系数 ,
最终的时间复杂度是
O(n)
;
因此使用快速选择算法..., 找数组中的第 K 大元素 , 时间复杂度是
O(n)
;
代码示例 :
class Solution {
/**
* 快速选择算法
* 第 K 大元素