1回答

liuyubobobo

2020-09-03

1）

因为在 arr[l, r] 的范围中，我们肯定能够找到第 k 大的元素（只要初始的 k 是合法的），所以，我们把递归终止条件变成了：

if(k == p) return arr[p];

这个意思就是，如果找到了，就返回这个元素；否则，继续递归地去找。

2）

当 l == r 时，在 partition 中会进行两次无意义的 swap 交换，这一步是不是没有必要？

你可以添加一个 if 语句来判断这种情况，对出现这种情况直接 return。但是要注意，这个 if 判断本身也是耗时的。到底是在所有的 partition 中都对 l 和 r 是否相等进行一次判断？还是在 l == r 的时候进行两次“无意义的交换”，那种性能更好，很难说。

不过，其实，在现代编程环境下，这样的性能考量并不重要。你可以选择你觉得最舒服，最容易理解的方式来实现。

3）

我们的代码不会走到 l > r 的情况。因为递归的过程一直保证了解在区间范围里。或者走到 if(k == p)，找到解，或者还没有找到解，其实，去左边找（l, p-1）或者去右边找 (p + 1, r) 一定是合法的区间范围。

继续加油！：）

0