请手写找出数组中第 k 大的数，并分别给出 O(n) 和 O(n log n) 两种解法，同时讲解思路。

回答思路

1. 能清晰说明两种解法的思路与适用场景
2. 能正确实现快速选择或基于堆的解法并分析平均与最坏复杂度
3. 能正确实现基于排序的解法并指出其复杂度
4. 能回答边界条件如 k 越界、重复元素处理