算法设计与分析实践-作业6-第k大的元素

1. 问题

• 用特定分治算法找出数组中第k大的元素。

2. 解析

• 如果|S1|等于k，则m*就是所要找的第 k 小的数；
• 如果|S1|大于等于k，归约为在S1中找第 k1 小的子问题，k 在子问题中相对位置不变，即k=k1
• 如果|S1|小于等于k，归约为在S2中找 k2 位置的子问题，k2 相对于 S2 子问题和 k 相对
• 于 S 的关系，即 k2= k-|S1|-1。（在 S 中找 k，就是在 S2中找 k2）

3. 设计

下面是处理该问题时的伪代码：

4.分析：

5. 源码

https://github.com/Ericjin1022/-suanfa