给定一个无序数组，找出其中第 k 大的元素。

答题要点

可以使用多种方法来找出无序数组中第 k 大的元素。一种简单的方法是先对数组进行排序，然后取第 k 大的元素。这种方法的时间复杂度为 O(n log n)，因为排序的时间复杂度通常为 O(n log n)。另一种更高效的方法是使用快速选择算法。快速选择算法是基于快速排序的思想，通过选择一个基准元素，将数组分为两部分，使得左边部分的所有元素都小于等于基准元素，右边部分的所有元素都大于基准元素。然后根据基准元素的位置与 k 的大小关系，决定在左边或右边继续查找。平均时间复杂度为 O(n)，最坏情况为 O(n^2)。具体步骤如下：选择一个基准元素，将数组分为两部分；计算基准元素的位置，如果位置等于 k，则返回该元素；如果位置大于 k，则在左边部分继续查找；如果位置小于 k，则在右边部分继续查找。