BFE.devAI解答 - JavaScript 代码题
45. 在未排序的数组中找到第K大的元素

一种解法是使用快速排序的思想，不过不需要对整个数组进行完整的排序，只需要不断地将比第K大的元素小的数排在数组左边，大的数排在右边，直到找到了第K大的数即可。

具体实现过程：

1. 以数组最后一个元素作为基准值，将数组中比该元素大的数都放在该元素的右边，比该元素小的数都放在该元素的左边，可以使用双指针法。
2. 判断该基准值的下标是否为K-1，如果是则返回该值，如果不是则根据下标关系在左边或右边继续递归查找第K大的元素。

代码实现如下：

function findKthLargest(nums, k) {
  const swap = (a, b) => {
    [nums[a], nums[b]] = [nums[b], nums[a]];
  };

  const partition = (left, right) => {
    const pivotIndex = right;
    let i = left;

    for (let j = left; j < right; j++) {
      if (nums[j] >= nums[pivotIndex]) {
        swap(i, j);
        i++;
      }
    }

    swap(i, pivotIndex);
    return i;
  };

  const quickSelect = (left, right) => {
    if (left === right) return nums[left];

    const pivotIndex = partition(left, right);

    if (pivotIndex === k - 1) {
      return nums[pivotIndex];
    } else if (pivotIndex > k - 1) {
      return quickSelect(left, pivotIndex - 1);
    } else {
      return quickSelect(pivotIndex + 1, right);
    }
  };

  return quickSelect(0, nums.length - 1);
}

// Example:
console.log(findKthLargest([3, 2, 1, 5, 6, 4], 2)); // Output: 5
console.log(findKthLargest([3, 2, 3, 1, 2, 4, 5, 5, 6], 4)); // Output: 4

时间复杂度为O(n)到O(n^2)，最好的情况下只需要排序一侧，复杂度为O(n)；最差的情况下每次基准值都是数组中最小或最大的数，需要排除所有元素，复杂度为O(n^2)。但由于该算法进行了一些优化，例如随机选取基准值，所以平均情况下时间复杂度为O(n)。